首页 > 代码库 > [2016CCPC]长春现场赛重现
[2016CCPC]长春现场赛重现
1002.公式，手算一下就能找到两个式子的关系，迭代一下就行。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 9; 5 int a[maxn], b[maxn]; 6 int n, p, q; 7 8 int gcd(int x, int y) { 9 return y == 0 ? x : gcd(y, x%y);10 }11 12 int main() {13 //freopen("in", "r", stdin);14 int T, _ = 1;15 scanf("%d", &T);16 while(T--) {17 printf("Case #%d: ", _++);18 scanf("%d", &n);19 for(int i = 1; i <= n; i++) scanf("%d", &a[i]);20 for(int i = 1; i <= n; i++) scanf("%d", &b[i]);21 p = b[n], q = a[n];22 int t;23 for(int i = n-1; i >= 1; i--) {24 int tp = b[i] * q;25 int tq = a[i] * q + p;26 p = tp; q = tq;27 t = gcd(p, q);28 p /= t; q /= t;29 }30 t = gcd(p, q);31 p /= t; q /= t;32 printf("%d %d\n", p, q);33 }34 return 0;35 }
1004.枚举所有情况打了一个表。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 22; 5 int n, cnt; 6 int a[maxn]; 7 vector<int> tmp, ret; 8 bool ok(int a, int b, int c) { 9 return a + b > c;10 }11 void table() {12 while(~scanf("%d", &n)) {13 if(n <= 3) {14 printf("0\n");15 continue;16 }17 cnt = n;18 for(int i = 0; i < maxn; i++) a[i] = i;19 int nn = 1 << n;20 for(int i = 0; i < nn; i++) {21 tmp.clear();22 for(int j = 0; j < n; j++) {23 if((1 << j) & i) {24 tmp.push_back(j+1);25 }26 }27 int mm = 1 << tmp.size();28 bool flag = 0;29 for(int j = 0; j < mm; j++) {30 ret.clear();31 for(int k = 0; k < tmp.size(); k++) {32 if((1 << k) & j) {33 ret.push_back(tmp[k]);34 }35 }36 if(ret.size() == 3) {37 sort(ret.begin(), ret.end());38 if(ok(ret[0],ret[1],ret[2])) flag = 1;39 }40 }41 if(!flag) cnt = min(cnt, n-(int)tmp.size());42 }43 printf("%d\n", cnt);44 }45 }46 47 int fk[25]={0,0,0,0,1,1,2,3,3,4,5,6,7,7,8,9,10,11,12,13,14};48 49 int main() {50 // freopen("in", "r", stdin);51 int T, _ = 1;52 scanf("%d", &T);53 while(T--) {54 scanf("%d", &n);55 printf("Case #%d: %d\n", _++, fk[n]);56 }57 }
1006.有一个很!@#的条件就是1<=2k<=n，这样的话最多的情况就是偶数连在一起，这时候和谐值正好是n/2。构造前半段是奇数后半段是偶数，然后看看多了几个数，用奇数把偶数隔开就行了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 11110; 5 int a[maxn]; 6 int n, k; 7 8 int main() { 9 // freopen("in", "r", stdin);10 int T, _ = 1;11 scanf("%d", &T);12 while(T--) {13 scanf("%d %d", &n, &k);14 k--;15 printf("Case #%d: ", _++);16 int x = 0, y = 1;17 for(int i = 1; i <= k + 1; i++) {18 x += 2;19 a[i] = x;20 }21 for(int i = k + 2; i <= n; i++) {22 if(x > y) {23 a[i] = y;24 y += 2;25 }26 else a[i] = y++;27 }28 for(int i = 1; i <= n; i++) printf("%d%c", a[i], i==n?‘\n‘:‘ ‘);29 }30 return 0;31 }
1007.Ramsey定理，我的思路是找到这个图的所有团，然后挨个组合一遍。看看一共有多少种。没
1008.仔细考虑一下复杂度就会明白，不管如何匹配，时间都不会到达O(n^2)，所以不用kmp，直接暴力就行了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 1001000; 5 int a[maxn], b[maxn]; 6 int n, m, p; 7 8 int main() { 9 // freopen("in", "r", stdin);10 int T, _ = 1;11 scanf("%d", &T);12 while(T--) {13 scanf("%d%d%d",&n,&m,&p);14 for(int i = 1; i <= n; i++) scanf("%d", &a[i]);15 for(int i = 1; i <= m; i++) scanf("%d", &b[i]);16 int ret = 0;17 for(int i = 1; i <= n; i++) {18 bool flag = 0;19 for(int j = 1; j <= m; j++) {20 if((i + (j - 1) * p > n) || (a[i+(j-1)*p] != b[j])) {21 flag = 1;22 break;23 }24 }25 if(!flag) ret++;26 }27 printf("Case #%d: %d\n", _++, ret);28 }29 return 0;30 }
1009.主席树+二分。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 200010; 5 int n,q,Case; 6 int a[maxn]; 7 typedef struct Node { 8 int l,r,sum; 9 }Node;10 Node tree[maxn*100];11 int rt[maxn],tot;12 void build(int &x,int l,int r) {13 x=++tot;tree[x].sum=0;14 if(l==r)return;15 int mid = (l + r) >> 1;16 build(tree[x].l,l,mid);17 build(tree[x].r,mid+1,r);18 }19 void update(int l,int r,int pos,int v,int y,int &x) {20 x=++tot;tree[x]=tree[y];tree[x].sum+=v;21 if(l==r)return;22 int mid = (l + r) >> 1;23 if(pos<=mid)update(l,mid,pos,v,tree[y].l,tree[x].l);24 else update(mid+1,r,pos,v,tree[y].r,tree[x].r);25 }26 int query(int t,int x,int l,int r) {27 if(l==r)return tree[t].sum;28 int mid = (l + r) >> 1;29 if(x<=mid)return query(tree[t].l,x,l,mid)+tree[tree[t].r].sum;30 return query(tree[t].r,x,mid+1,r);31 }32 33 int main() {34 // freopen("in","r",stdin);35 int T, _ = 1;36 scanf("%d",&T);37 while(T--) {38 scanf("%d%d",&n,&q);39 map<int,int>h;40 for(int i=1;i<=n;i++) {41 scanf("%d",&a[i]);42 }43 tot=0;build(rt[0],1,n);44 for(int i=1;i<=n;i++) {45 if(!h.count(a[i])) {46 update(1,n,i,1,rt[i-1],rt[i]);47 }48 else {49 update(1,n,h[a[i]],-1,rt[i-1],rt[i]);50 update(1,n,i,1,rt[i],rt[i]);51 }52 h[a[i]]=i;53 }54 int ret=0;55 printf("Case #%d:", _++);56 while(q--) {57 int tl,tr;58 scanf("%d%d",&tl,&tr);59 tl=(tl+ret)%n+1, tr=(tr+ret)%n+1;60 int l=min(tl,tr), r=max(tl,tr);61 int num=query(rt[r],l,1,n);62 int k=(num+1)/2;63 if(k<=1) {64 ret=l;printf(" %d",ret);65 continue;66 }67 int x = l, mid;68 while(l <= r) {69 mid = (l + r) / 2;70 int tmp = query(rt[mid],x,1,n);71 if(tmp >= k) {72 ret = mid;73 r = mid - 1;74 }75 else l = mid + 1;76 }77 printf(" %d",ret);78 }79 puts("");80 }81 return 0;82 }
1010.构造，无脑取前半段减一，然后对称地复制过去，这样被减数每次这么减总会剪掉一半的长度。我的实现需要特别注意一个情况就是10的时候直接给出结果就行了，否则会无限给出00。
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 1100; 5 char s[maxn]; 6 char t[maxn], r[maxn]; 7 vector<string> ret; 8 int n, m; 9 10 void sub(char* ca, char* cb, char* cc) {11 int a[maxn], b[maxn];12 memset(a, 0, sizeof(a));13 memset(b, 0, sizeof(b));14 int la = strlen(ca);15 int lb = strlen(cb);16 for(int i = 0; i < la; i++) a[i] = ca[la-i-1] - ‘0‘;17 for(int i = 0; i < lb; i++) b[i] = cb[lb-i-1] - ‘0‘;18 for(int i = 0; i < la; i++) {19 if(a[i] >= b[i]) a[i] -= b[i];20 else {21 a[i] = a[i] - b[i] + 10;22 a[i+1]--;23 }24 }25 int p = maxn;26 while(p--) if(a[p] != 0) break;27 for(int i = p; i >= 0; i--) cc[p-i] = a[i] + ‘0‘;28 }29 30 int main() {31 //freopen("in", "r", stdin);32 int T, _ = 1;33 scanf("%d", &T);34 while(T--) {35 scanf("%s", s);36 ret.clear();37 while(1) {38 n = strlen(s);39 if(strcmp("10", s) == 0) {40 ret.push_back("9");41 ret.push_back("1");42 break;43 }44 if(n == 1) {45 ret.push_back(s);46 break;47 }48 bool ex = 0;49 for(int i = n/2; i >= 0; i--) {50 if(s[i] != s[n-i-1]) {51 ex = 1;52 break;53 }54 }55 if(!ex) {56 ret.push_back(s);57 break;58 }59 memset(t, 0, sizeof(t));60 memset(::r, 0, sizeof(r));61 if(n == 2) {62 char tmp = min(s[0], s[1]);63 if(tmp != ‘0‘) t[0] = t[1] = tmp;64 else t[0] = t[1] = max(s[0], s[1]) - 1;65 }66 else {67 int l, r;68 if(n & 1) {69 for(int i = 0; i <= n/2; i++) t[i] = s[i];70 sub(t, "1", ::r); m = strlen(::r);71 memset(t, 0, sizeof(t));72 for(int i = 0; i < m; i++) t[i] = ::r[i];73 l = m - 2; r = m;74 // if(m * 2 != n) l++;75 while(l >= 0) t[r++] = t[l--];76 }77 else {78 for(int i = 0; i < n/2; i++) t[i] = s[i];79 sub(t, "1", ::r); m = strlen(::r);80 memset(t, 0, sizeof(t));81 for(int i = 0; i < m; i++) t[i] = ::r[i];82 l = m - 1; r = m;83 // if(m * 2 != n) l--;84 while(l >= 0) t[r++] = t[l--];85 }86 }87 ret.push_back(t);88 memset(r, 0, sizeof(r));89 sub(s, t, r);90 memcpy(s, r, sizeof(r));91 }92 printf("Case #%d:\n", _++);93 printf("%d\n", ret.size());94 for(int i = 0; i < ret.size(); i++) {95 printf("%s\n", ret[i].c_str());96 }97 }98 return 0;99 }
[2016CCPC]长春现场赛重现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。