SPS的格子 【构造】
【题目描述】
SPS有n个格子，现在他要让你对这n个格子染色，每个格子可以染色成0~9。
因为SPS希望完美，所以他想，如果a+b=c，那么如果格子a与格子b颜色相同，那么格子c与格子a颜色就不能相同。
请你构造出方案。
30:n≤210−1
60:n≤310−1
100:n≤25000
【题解】
题目来源：2016-2017 CT S03E02: Codeforces Trainings Season 3 Episode 2 Problem I
当时比赛属于全程懵逼状态。
首先n≤210−1可以用暴力得出结果。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | # include <stdio.h>using namespace std;int n, a[25010];bool okk=0;inline void fk(int step) { if(okk == 1) return; if(step == n+1) { for (int i=1; i<=n; ++i) { printf("%d", a[i]-1); } okk=1; return ; } for (int i=1; i<=10; ++i) { if(okk == 1) return; a[step] = i; bool ok=1; for (int j=1; j<=step/2+1; ++j) { if(a[j] == a[step-j] && a[j] == a[step]) { ok=0; break; } } if(!ok) continue; fk(step+1); }}int main() { scanf("%d", &n); fk(1); return 0;} |
然后黄文翰学长提供了一种康托三分集的思想。
具体就是类似于这样
121333121444444444121333121555555555555555555555555555....
是一种分形构造。很明显满足题目要求，这样就能过60%的数据啦！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | # include <stdio.h>using namespace std;int n;int a[60000];inline void sf(int l, int r, int num) { if(l == r) {a[l] = num; return;} int mid1 = l+(r-l+1)/3, mid2 = r-(r-l+1)/3; //printf("%d %d %d %d\n", l, r, mid1, mid2); for (int i=mid1; i<=mid2; ++i) a[i] = num; sf(l, mid1-1, num+1); sf(mid2+1, r, num+1); }int main() { //freopen("a.txt", "w", stdout); scanf("%d", &n); if(n<=19683) { sf(1, 19683, 0); for (int i=1; i<=n; ++i) printf("%d", a[i]); } else { for (int i=1; i<=n; ++i) printf("0"); } return 0;} |
然后今天早上起来，cf上有人给了一种新的构造方法，能通过本题。
excited!!!
这样就有满分啦！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | # include <stdio.h># include <vector># include <algorithm>using namespace std;vector<int> t[11];int three[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049};int a[77777], n;int main() { for (int i=1; i<=10; ++i) t[i].clear(); t[1].push_back(1); for (int i=1; i<=9; ++i) { for (int j=1; j<=i; ++j) { int sz = t[j].size(); for (int k=0; k<sz; ++k) t[j].push_back(t[j][k]+three[i]); sort(t[j].begin(), t[j].end()); vector<int> :: iterator iter = unique(t[j].begin(), t[j].end()); t[j].erase(iter, t[j].end()); } for (int j=(three[i]+1)/2; j<=three[i]; ++j) t[i+1].push_back(j); } for (int i=1; i<=10; ++i) { for (int j=0; j<t[i].size(); ++j) a[t[i][j]] = i-1; } scanf("%d", &n); for (int i=1; i<=n; ++i) printf("%d", a[i]); return 0;} |
2023年2月11日 18:23
10th Question Paper 2024 is Get Available by the Board of Secondary Education. The Model Question Paper for class 10th will deliver in online mode on the authority site. The Model Paper will comprise of the subject-wise New Question Paper, day, timings, 10th Question Paper 2024 and significant guidelines for test day. In this article, the up-and-comer will get the data about the 10th Class Latest Question Paper 2024 including delivering PDF and how to download the Latest Question Paper.