参考资料：
[1]: the Chinese Editoria
题意：
x个人投赞同票，y人投反对票，z人不确定；
这 z 个人由你来决定是投赞同票还是反对票；
判断 x 与 y 的相对大小是否确定？
题解：
如果 x == y && z == 0，输出 ‘0‘；
如果 x-y > z，输出 ‘+‘；
如果 y-x > z，输出 ‘-‘；
反之，输出 ‘?‘；
AC代码：
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define INF 0x3f3f3f3f 4 #define ll long long 5 #define mem(a,b) memset(a,b,sizeof(a)) 6 #define memF(a,b,n) for(int i=0;i <= n;a[i++]=b); 7 const int maxn=1e3+50; 8 9 int x,y,z; 10 11 char *Solve() 12 { 13 if(x == y && z == 0) 14 return "0"; 15 if(x-y > z) 16 return "+"; 17 if(y-x > z) 18 return "-"; 19 return "?"; 20 } 21 int main() 22 { 23 // freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin); 24 scanf("%d%d%d",&x,&y,&z); 25 puts(Solve()); 26 27 return 0; 28 }
题意：
给你 n 个棋子，求满足 "for all pairs of pieces i and j, |ri−rj|+|ci−cj| ≥ |i−j|."的最小的方形棋盘的列；
题解：
方形棋盘的右下角(m,m)与左上角(1,1)的距离为 2×(m-1)；
①找到 2×(m-1) ≥ n-1 的最小的 m；
②将 1~n-1 个棋子从第一行开始填充，第一行填充完，填充最后一列；
AC代码：
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define memF(a,b,n) for(int i=0;i <= n;a[i++]=b); 4 #define INF 0x3f3f3f3f 5 const int maxn=2e5+50; 6 7 int n; 8 9 void Solve() 10 { 11 int m=(n+2)/2; 12 printf("%d\n",m); 13 int x=1,y=1; 14 for(int i=1;i < n;++i) 15 { 16 printf("%d %d\n",x,y); 17 if(y < m)///先填充第一行 18 y++; 19 else 20 x++; 21 } 22 printf("%d %d\n",m,m); 23 } 24 int main() 25 { 26 scanf("%d",&n); 27 Solve(); 28 29 return 0; 30 }
题意：
有 2n 张牌，其中 n 张标号 1~n，其余 n 中为空牌；
从这 2n 张牌中拿出 n 张放在手中，剩余的 n 张摞在桌子上（牌堆）；
你可以进行如下操作：
将手中的任意一张牌插入到牌堆的底部，并将牌堆顶端的牌放入手中；
求最少的操作，使得摞在桌子上的 n 张牌从顶端到底端为 1,2,....,n；
题解（来自对参考资料的理解）：
第一句话很好理解，主要是 “答案为 max(...)”这句话不太好理解，下面说说我的进一步理解：
最终结果就是 1~n 摞在桌子上，并且有序；
那么，存在牌k，在经过操作后，使得[1,2,...,k]在牌堆的底端，并且接下来的操作只用标号为[k+1,....,n]的牌，将其依次插入牌堆的底端；
那么，这种情况下，答案就为 p[k]+1+n-k；
其中 p[k]+1 是将牌 k 插入牌堆底端需要的最小操作，n-k是将[k+1,....,n]依次插入牌堆的最小操作；
AC代码：
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define INF 0x3f3f3f3f 4 const int maxn=2e5+50; 5 6 int n; 7 int a[maxn]; 8 int b[maxn]; 9 int p[maxn];///p[i]:第i张牌在b中的位置，如果在a中，那么p[i]=0; 10 11 int F()///判断是否可以只将标号牌插入牌堆的底端使得最终状态满足条件 12 { 13 if(!p[1]) 14 return INF; 15 int cur=2; 16 for(;p[cur] == p[1]+cur-1;cur++); 17 if(p[cur-1] == n)///[1,2,...,cur-1]在b中最后的位置 18 { 19 int k=cur; 20 /** 21 在依次将第k(k∈[cur,n])张牌插入底部的时候要确保k在手上 22 如何确保k在手上呢？ 23 假设[cur,k-1]成功插入到底部； 24 那么，这k-cur牌的插入势必会使得b中的前k-cur张牌拿到手中； 25 那么，只要b中前k-cur张牌含有k就行； 26 也就是p[k]<=k-cur; 27 */ 28 for(;k <= n && p[k] <= k-cur;k++); 29 if(k > n)///如果k=n+1,那么只操作[cur,n]便可满足条件 30 return n-(cur-1); 31 } 32 return INF; 33 } 34 int G() 35 { 36 /** 37 ①如果[1,..,i]中标号为x的牌，x在b中的位置在i之后 38 也就是说 x<i,p[x]>p[i]; 39 那么 p[x]+1+n-x > p[i]+1+n-i； 40 对于这种情况，ans只会取x对应的操作次数 41 ②如果经过p[i]+1次操作后使得[1,...i]插入牌堆的底端 42 但是，i之后存在标号为x,y的牌，x<y,p[x]>p[y] 43 那么，[i+1,...,n]是没法依次插入牌堆的 44 但，答案会是p[i]+1+n-i吗？ 45 易得p[x] >= p[i]+2 46 第i张牌的操作次数为 p[i]+1+n-i; 47 第x张牌的操作次数为 p[x]+1+n-x; 48 两者做差得 p[x]+1+n-x-(p[i]+1+n-i)=p[x]-p[i]+i > 0 49 所以，ans只会取x对应的操作次数，而不会取i对应的操作次数 50 */ 51 int ans=0; 52 for(int i=1;i <= n;++i) 53 ans=max(ans,p[i]+1+n-i); 54 return ans; 55 } 56 int main() 57 { 58 scanf("%d",&n); 59 for(int i=1;i <= n;++i) 60 { 61 scanf("%d",a+i); 62 p[a[i]]=0; 63 } 64 for(int i=1;i <= n;++i) 65 { 66 scanf("%d",b+i); 67 p[b[i]]=i; 68 } 69 printf("%d\n",min(F(),G())); 70 71 return 0; 72 }
Codeforces Round #564 (Div. 2)
原文：https://www.cnblogs.com/violet-acmer/p/10989957.html
