t1 陪审团
题目
【题目描述】
陪审团制度历来是司法研究中的一个热议话题,由于陪审团的成员组成会对案件最终的结果产生巨大的影响,诉讼双方往往围绕陪审团由哪些人组成这一议题激烈争夺。小 w提出了一个甲乙双方互相制衡的陪审团成员挑选方法:假设共有 n 名候选陪审团成员,则由甲先提名 s 位候选人,再由乙在甲提名的 s 位候选人中选出t名,作为最终的陪审团成员。显然这里应当有 n≥s≥t 。假设候选人k对甲、乙的有利程度都可以用一个二元组( xk ,yk )来表示,x.越大说明候选人 k 对甲越有利, yk 越大则对乙越有利。在此前提下,双方的目标都变得明确:甲要最大化最终陪审团 t 人的 x 之和,最小化 y之和,乙则反之。
现在甲方决定聘请你为律师,并且事先得知了乙方律师的策略:乙方律师会在你提名的 s名候选人中选出 t 名使得这 t 人的 y 值之和最大,再保证 y 值之和最大的前提下使得 x值之和尽量小(在对乙方最有利的前提下对甲方最不利)。
现在你应当慎重地提名 s 位候选人使得最终由乙方律师确定的 t 人 x 值和最大,若有多种方案,则应再使被乙方排除掉的 t-s 人的 y 值和尽量大,在此基础上最大化 s 人的 x值之和。 你的当事人并不关心你提名的具体是哪些人,只要你告诉他你提名的s人的x值之和与y值之和。
【输入格式】
第一行包含三个整数n,s,t。
接下来nn行,每行两个整数分别表示xk,yk。
【输出格式】
共一行两个整数,分别为x值之和与y值之和。
【数据规模】
对于30%的测试数据n≤20
对于50%的测试数据n≤100
对于100%的测试数据n≤100000,x,y≤1000000
解析
因为乙会从s个中选出t个对自己有利的,所以剩下s-t个就是不选的,所以n个中一定至少有s-t个未被选中,这就是y最小的s-t个。
所以我们先按y的大小排序一遍,最后的s-t个假设我们先选了,乙就没有选择的余地了。
然后我们按x的大小排序一遍,这样我们可以保证自己得到的结果是最大的。
但到了这里还有一个漏洞,那就是s-t的要尽可能大(多个方案下)。因此我们将第一遍的t个选择标记,在按y的从大到小排序若y值相同,则x值小的在后面。这样从后往前先找到自己的第一个标记处,往后重新选择s-t个,这s-t个肯定是y比前面的小,但是最大的,且s的x之和是最大的。
code
![泉五培训Day5](https://www.ctvol.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; long long n,s,t,sumx,sumy; struct person{ int x,y; bool cho; }per[105000]; bool cmp1(person a,person b) { if(a.y==b.y) return a.x>b.x; return a.y<b.y; } bool cmp2(person a,person b) { if(a.x==b.x) return a.y>b.y; return a.x>b.x; } bool cmp3(person a,person b) { if(a.y!=b.y) return a.y>b.y; if(a.x!=b.x) return a.x>b.x; return ((int)(a.cho)-(int)(b.cho)>0); } int read() { char ch; bool flag=false; int num=0; ch=getchar(); while(ch>'9'||ch<'0') { if (ch=='-') flag=true; ch=getchar(); } while(ch>='0'&&ch<='9') { num=num*10+(ch-'0'); ch=getchar(); } if (flag==true) num*=-1; return num; } int main() { n=read(),s=read(),t=read(); for(int i=1;i<=n;i++) { per[i].x=read(); per[i].y=read(); } sort(per+1,per+n+1,cmp3); sort(per+1,per+1+n-s+t,cmp2); for(int i=1;i<=t;i++) per[i].cho=1; sort(per+1,per+n+1,cmp3); int first; for(int i=n;i>=1;i--) if(per[i].cho) { first=i; break; } int i; for(i=t+1,first++;i<=s;i++,first++) per[first].cho=1; for(int i=1;i<=n;i++) if(per[i].cho) { sumx+=per[i].x; sumy+=per[i].y; } cout<<sumx<<sumy; return 0; }
view code
t2 shine
题目
【题目描述】
今天是noip初赛,capo坐在考场上看着手中的初赛试卷,非常无聊,早已被钦点进入复赛的她在卷子上做了奇怪的事。 卷子可以看成一张n×m的方格纸,capo手中有一支笔头截面是x×y矩形的笔,她在试卷上画下了一道痕迹,痕迹是由笔在纸面上做平行网格的运动画出的,笔不可以旋转,刚开始笔头截面的边平行与网格,每次移动,笔头只会向下或者向右移动一格。 阅卷老师octavia看到了这张卷子,他对capo的笔十分好奇,于是他想从笔迹中猜出笔头截面大小,请你告诉他x×y的最小值。
【输入格式】
第一行两个整数n,m表示卷子大小。 下面n行,每行m个字符,x
表示有笔迹,.
表示没有。
【输出格式】
一行一个整数,表示最小的x×y,无解输出-1
。
【数据规模】
subtask 1(10’):n,m≤10
subtask 2(30’):n,m≤100
subtask 3(10’):n=1,m≤1000
subtask 4(20’):n=2,m≤1000
subtask 5(30’):n,m≤1000
解析
现在左上方找到起点,再从起点向右方和下方延伸,
设最大延伸长度为x0,y0,显然x=x0和y=y0中必定有一个满足,设其中一个满足,再枚举另一个即可。
code
![泉五培训Day5](https://www.ctvol.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
#include<cstdio> #include<algorithm> using namespace std; #define sum(x1,y1,x2,y2) (s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]) int n,m; char c[1005][1005]; int s[1005][1005]; int ans=1000000000; int dfs(int x,int y,int wx,int wy) { if(sum(x,y+1,x+wx-1,y+wy)==wx*wy)return wx+dfs(x,y+1,wx,wy); if(sum(x+1,y,x+wx,y+wy-1)==wx*wy)return wy+dfs(x+1,y,wx,wy); return 0; } int main() { freopen("shine.in","r",stdin); freopen("shine.out","w",stdout); scanf("%d%dn",&n,&m); int flag=0,px,py; for(int i=1;i<=n;i++) gets(c[i]+1); for(int i=1;i<=n+1;i++) for(int j=1;j<=m+1;j++) { if(c[i][j]=='x') { if(!flag){flag=1;px=i;py=j;} s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+1; } else s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]; } int tmp,wx,wy; for(tmp=px;c[tmp][py]=='x';tmp++); wx=tmp-px; for(int i=py;c[px][i]=='x';i++) if(sum(px,py,px+wx-1,i)==wx*(i-py+1)&&dfs(px,py,wx,i-py+1)+wx*(i-py+1)==s[n][m]) ans=min(ans,wx*(i-py+1)); for(tmp=py;c[px][tmp]=='x';tmp++); wy=tmp-py; for(int i=px;c[i][py]=='x';i++) if(sum(px,py,i,py+wy-1)==(i-px+1)*wy&&dfs(px,py,i-px+1,wy)+(i-px+1)*wy==s[n][m]) ans=min(ans,(i-px+1)*wy); if(ans<=n*m) cout<<ans; else printf("-1n"); return 0; }
view code
t3 小p的世界
题目
【题目描述】
小p的世界是一棵n(n<=1000)个节点的有根树(根为1),树上的每条边上都会有一个泡泡怪,小p从根节点开始移动(可以往回走),每经过一条边,小p都会打败边上的泡泡怪同时得到相应的泡泡气(每只泡泡怪只能被打败一次),已知 小p经过一条边需要花费 1 天时间,小p想知道自己晋级泡泡帝(泡泡气大于等于 k)至少需要的天数(如果 小p永远达不到泡泡帝,输出“qaq”
(不带引号))
【输入格式】
第一行两个用空格隔开的正整数 n,k。(1<=n<=1000,1<=k<=1000)
接下来 n – 1行每行三个用空格隔开的正整数 a,b,c,表示树上 a 与 b 之间连了一条边,打败边上的泡泡怪获得 c 点泡泡气(1<=a,b<=n,1<=c<=k/2,保证 a 是 b 的父亲)
【输出格式】
总共一行一个整数,表示答案
【数据规模】
保证树中每个节点至多两个孩子。
20 个测试点,每个测试点 5 分
1.testtest 1~4: n,k <= 10
2.tsettset 5~20:n,k <= 1000 数据有梯度且大多随机,尽量优化自己的程序
解析
分别设置f[i][j]和g[i][j]. f[i][j]表示从i出发,不返回i得到j点泡泡气最少天数。
g[i][j]表示最终要返回i,其他和f数组一样,初始化f[i][0]=g[i][0]=0
转移时分两种情况,有一个孩子就直接赋值,两个孩子分两种情况走
code
![泉五培训Day5](https://www.ctvol.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int size=1000+5; const int inf=1e8; int n,k; int go[size][size]; int re[size][size]; int child[size][2]; int child_v[size][2]; int sum=0; int read() { int num=0,w=1; char ch=getchar(); while(ch<'0' || ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch<='9' && ch>='0') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } inline void init() { n=read();k=read(); for(int i=1;i<n;i++) { int a=read(),b=read(),c=read(); child_v[a][child[a][0] != 0]=c; child[a][child[a][0] != 0]=b; sum+=c; } } int root = 1; void dfs1(int k,int sum) { if(sum>=k) { child_v[k][0]=child_v[k][1]=0; return; } if(child[k][0]) dfs1(child[k][0],sum+child_v[k][0]); if(child[k][1]) dfs1(child[k][1],sum+child_v[k][1]); } void dfs(int k) { go[k][0]=re[k][0]=0; int lc=child[k][0],rc=child[k][1]; if(!lc) return; dfs(lc); if(rc) dfs(rc); int chongjg=child_v[k][0];//走左节点能得到的泡泡气 for(int i=0;i<=k-chongjg;i++) { if(go[lc][i]>inf) break ; if(go[lc][i]+1<go[k][i+chongjg]) go[k][i+chongjg]=go[lc][i]+1; if(re[lc][i]+2<re[k][i+chongjg]) re[k][i+chongjg]=re[lc][i]+2; } //如果不存在右节点 if(rc==0) { for(int i=k;i>=0;i--) //枚举每种情况 { if(go[k][i+1]<go[k][i]) go[k][i]=go[k][i+1]; if(re[k][i+1]<re[k][i]) re[k][i]=re[k][i+1]; } return ; } chongjg=child_v[k][1];//走右节点能得到的泡泡气 for(int i=0;i<=k-chongjg;i++) { if(go[rc][i]>inf) break; if(go[rc][i]+1 < go[k][i+chongjg]) go[k][i+chongjg]=go[rc][i]+1; if(re[rc][i]+2 < re[k][i+chongjg]) re[k][i+chongjg]=re[rc][i]+2; } chongjg=child_v[k][0]+child_v[k][1];//两个节点都走能得到的泡泡气 for(int i=0;i<=k-child_v[k][0];i++) { if(go[lc][i]>inf) break; for(int j=0;j<=k-chongjg-i;j++) { if(go[rc][j]>inf) break; if(go[lc][i]+re[rc][j]+3<go[k][i+j+chongjg]) go[k][i+j+chongjg]=go[lc][i]+re[rc][j]+3; if(re[lc][i]+go[rc][j]+3<go[k][i+j+chongjg]) go[k][i+j+chongjg]=re[lc][i]+go[rc][j]+3; if(re[lc][i]+re[rc][j]+4<re[k][i+j+chongjg]) re[k][i+j+chongjg]=re[lc][i]+re[rc][j]+4; } } for(int i=k;i>=0;i--) { if(go[k][i+1]<go[k][i]) go[k][i]=go[k][i+1]; if(re[k][i+1]<re[k][i]) re[k][i]=re[k][i+1]; } } int main() { init(); dfs1(root,0); if(sum<k){puts("qaq");return 0;}; memset(go,63,sizeof(go)); memset(re,63,sizeof(re)); dfs(1); cout<<go[1][k]; return 0; }
view code
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605312.html