自媒体可做外链网站,建立网站tk,如何渗透wordpress的网站,网站有哪些内容前言
……终于改完了#xff0c;像之前小L一样崩溃。今天C组和B组一起做题#xff0c;所以…… 正题 题目1#xff1a;教主的花园#xff08;jzoj1792#xff09;
一平面直角坐标系#xff0c;在x轴的位置建立一堵墙#xff0c;墙上有n道门#xff0c;给出门的位置像之前小L一样崩溃。今天C组和B组一起做题所以…… 正题 题目1教主的花园jzoj1792
一平面直角坐标系在x轴的位置建立一堵墙墙上有n道门给出门的位置询问两个坐标的距离曼哈顿。
输入输出建议无视
Input
输入的第1行为一个正整数N为屏障上入口的个数。 第2行有N个整数a1, a2, …, aN之间用空格隔开为这N个入口的横坐标。 第3行为一个正整数M表示了M个询问。 接下来M行每行4个整数x1, y1, x2, y2有y1与y2均不等于0表示了一个询问从(x1, y1)到(x2, y2)的最短路。
Output
输出共包含m行第i行对于第i个询问输出从(x1, y1)到(x2, y2)的最短路距离是多少。
Sample Input
2 2 -1 2 0 1 0 -1 1 1 2 2
Sample Output
4 2
解题思路
有三种情况 1. 坐标之间不隔墙 2. 坐标之间隔墙并且最近的墙在两个坐标之间 3. 坐标之间隔墙并且最近的墙在两个坐标之间 然后前两种情况之接输出曼哈顿距离第三种情况输出两个距离门的距离和。 用二分确定最近的门
代码
#includecstdio
#includealgorithm
using namespace std;
int n,a[100001],m,x,y,zx,zy,l,r,mid,last;
bool ok;
int abs(int x)
{if (x0) return 0-x;else return x;
}
int main()
{scanf(%d,n);for (int i1;in;i)scanf(%d,a[i]);sort(a1,a1n);//排序scanf(%d,m);for (int i1;im;i){scanf(%d%d%d%d,x,y,zx,zy);//输如if (y0 zy0 || y0 zy0)//如果中间隔墙{l1;rn;last2147483647;//last记录离门最近距离oktrue;while (lr){mid(int)(lr)/2;if (zxa[mid] xa[mid] || zxa[mid] xa[mid])//如果门在中心{lmid;last0;break;//退出}if (min(abs(a[mid]-x),abs(a[mid]-zx))*2last)//如果找到更近的距离{lastmin(abs(a[mid]-x),abs(a[mid]-zx))*2;//记录if (a[mid]x) lmid;else rmid;}elseif (a[mid]x) lmid1;else rmid-1;}printf(%d\n,lastabs(x-zx)abs(zy-y));//输出}else printf(%d\n,abs(zx-x)abs(zy-y));//输出}
} 题目2教主泡嫦娥jozj1793
有一个环形山地有n个落脚点可以从任意落脚点任意状态出发。每个落脚点的代价为 当教主从第i个落脚点走到第j个落脚点的时候i和j相邻 j的海拔高于i的海拔如果教主处于上升状态教主需要耗费两段高度差的绝对值的体力否则耗费高度差平方的体力。 j的海拔低于i的海拔如果教主处于下降状态教主需要耗费两段高度差的绝对值的体力否则耗费高度差平方的体力。 求走一圈的最小代价
输入输出建议无视
Input
输入的第一行为两个正整数N与M即落脚点的个数与切换状态所消耗的体力。 接下来一行包含空格隔开的N个正整数表示了每个落脚点的高度题目保证了相邻落脚点高度不相同。
Output
输出仅包含一个正整数即教主走一圈所需消耗的最小体力值。 注意C选手建议使用cout输出long long类型整数。
Sample Input
6 7 4 2 6 2 5 6
Sample Output
27
解题思路
如果枚举落脚点肯定会超时所以我们就不能这么做。 用f[i][j][k]表示在第i个落脚点状态为j在当前有没有改变状态。 然后O(n)的时间复杂度轻易过 动态转移方程 f[i][j][0]f[i-1][j][0]abs(a[i]-a[i-1]) 直接走过 f[i][j][1]min(f[i-1][j][1],min(f[i-1][j^1][0],f[i-1][j^1][1])m)abs(a[i]-a[i-1]) 改变状态
f[i][j][0]f[i-1][j][0]pows(a[i]-a[i-1]) f[i][j][1]min(f[i-1][j][1],min(f[i-1][j^1][0],f[i-1][j^1][1])m)pows(a[i]-a[i-1]) 在这题被逼疯默默AC不想说话
代码
#includecstdio
#includecstring
#includeiostream
using namespace std;
long long f[10001][2][2],ans;
int a[10001],n,m;
long long abs(long long x)
{if (x0) return 0-x;else return x;
}
long long pows(long long x)
{return x*x;}
void dp()
{f[0][1][1]f[0][0][1]1e16-1;for (int i1;in;i)for (int j0;j2;j)if ((a[i]a[i-1])^j){f[i][j][0]f[i-1][j][0]abs(a[i]-a[i-1]);f[i][j][1]min(f[i-1][j][1],min(f[i-1][j^1][0],f[i-1][j^1][1])m)abs(a[i]-a[i-1]);}else{f[i][j][0]f[i-1][j][0]pows(a[i]-a[i-1]);f[i][j][1]min(f[i-1][j][1],min(f[i-1][j^1][0],f[i-1][j^1][1])m)pows(a[i]-a[i-1]);}//动态转移
}
int main()
{scanf(%d%d,n,m);for (int i0;in;i){scanf(%d,a[i]);}a[n]a[0];memset(f,0ll,sizeof(f));dp();//dp一次ansmin(min(f[n][0][0],f[n][0][1]),min(f[n][1][0],f[n][1][1]));//取最小情况memset(f,0ll,sizeof(f));f[0][0][0]1e16-1;//从f[0][1][0]推过去dp();//dp一次ansmin(ans,f[n][1][1]-m);//取值memset(f,0ll,sizeof(f));f[0][1][0]1e16-1;//从f[0][0][0]推过去dp();//dp一次ansmin(ans,f[n][0][1]-m);//取值coutansendl;
} 题目3保镖排队jzoj1794
有n个保镖除第一个保镖外每个保镖都有一个上司每个上司的下属都有在上司心目中的武力值。排队要求 ①互为上司-下属的两个保镖上司在前下属在后 ②对于一个保镖的所有下属武功实力较强的在前较弱的在后。 求排队方案数
输入输出建议无视
Input
输入的第一行为一个正整数T表示了数据组数。 对于每组数据 第一行为一个正整数N。 接下来N行每行描述一个保镖。 第i1行会有一个整数K代表第i个保镖的下属个数接下来K个数代表第i个保镖的下属按照武功实力从高到低的编号。
Output
输出包括C行每行对于每组数据输出方案数mod 10007后的结果。
Sample Input
2 5 2 2 3 2 4 5 0 0 0 7 2 2 3 2 4 5 2 6 7 0 0 0 0
Sample Output
3 10
解题思路
首先想到的是树形dp由于保镖一没有上司所以一定是根。然后就是插空问题了将3个保镖插入到3个空中用组合的方法求插空方案数。用杨辉三角求组合。然后树形dp
代码
#includecstdio
#includecstring
using namespace std;
struct line{int y,next;
}a[10001];//邻接表
int f[1001],s,ls[1001],n,k,t,w,head,num[1001];
int cost[1002][1002];
void dp(int x)
{int qls[x];f[x]1;if (q0){num[x]1;return;//没有子树}while (q!0){dp(a[q].y);num[x]num[a[q].y];//累计f[x]((f[x]*f[a[q].y])%10007)*(cost[num[x]-1][num[a[q].y]-1])%10007;//求方案数qa[q].next;}num[x];//算上自己
}
int main()
{cost[0][0]1;for (int i1;i1001;i)for (int j1;ji;j){cost[i][0]1;cost[i][j](cost[i-1][j]cost[i-1][j-1])%10007;}//杨辉三角scanf(%d,t);for (int ti1;tit;ti){w0;s0;memset(ls,0,sizeof(ls));memset(f,0,sizeof(f));memset(num,0,sizeof(num));//初始化scanf(%d,n);for (int i1;in;i){scanf(%d,k);for(int j1;jk;j){scanf(%d,a[w].y);a[w].nextls[i];ls[i]w;}}dp(1);//dpprintf(%d\n,f[1]);}
} 题目4教主的别墅jzoj1795
有N个人有男有女分成m段连续的部分求分割的最小和最大字典序。
输入输出建议无视
Input 输入的第1行为两个正整数N与M用空格分隔。 第2行包含一个长度为N的串仅由字符组成第i 个字符为0表示在这个位置上的LHXee为女生若为1则为男生。
Output 输出文件包含两行每行M个正整数正整数之间用空格隔开行末无多余空格。这M个正整数从左到右描述了你所分的每个组的人数。 第1行为字典序最小的方案第2行为字典序最大的方案。
Sample Input
8 3 11001100
Sample Output
1 2 5 5 2 1
解题思路
这道题贪心竟然能过 深搜TLE贪心只能过样例 听某dalao讲用前缀和到第i个房间的男女差值绝对值然后每个房间最大差值为
summsumm
\frac{sum}{m} 然后正推一次反推一次。#includecstdio
#includeiostream
using namespace std;
int n,m,sum[5000002],ans,anss,t,last,w,a[100002];
char c;
int abs(int x)
{if (x0) return 0-x;else return x;
}//绝对值
int main()
{scanf(%d%d\n,n,m);for (int i1;in;i){cinc;if (c0) sum[i]-1;else sum[i]1;sum[i]sum[i-1];}ansabs(sum[n])/m;//求最大差值if (abs(sum[n])%m!0) ans;//向上取整if (sum[n]0){int l0;for (int i1;in;i)if (sum[i]0) l;if (lm) ans0;else ans1;//能否做到没有差值}tm;last0;for (int i1;in;i){anssabs(sum[n]-sum[i])/(t-1);if (abs(sum[n]-sum[i])%(t-1)!0) anss;if (abs(sum[i]-sum[last])ans anssans){printf(%d ,i-last);lasti;t--;if (t1) break;}}//查找printf(%d\n,n-last);ansabs(sum[n])/m;if (abs(sum[n])%m!0) ans;if (sum[n]0){int l0;for (int i1;in;i)if (sum[i]0) l;if (lm) ans0;else ans1;}tm;lastn;w0;for (int in-1;i1;i--){anssabs(sum[i])/(t-1);if (abs(sum[i])%(t-1)!0) anss;if (abs(sum[last]-sum[i])ans anssans){a[w]last-i;lasti;t--;if (t1) break;}}//倒着查找a[w]last;//记录for (int iw;i1;i--) printf(%d ,a[i]);
}
