「CF260X」Codeforces Round #158 (Div. 2)
A. Adding Digits
模拟，每次可以根据当前模的结果，得出下一个添加的数字
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } bool flag; int a,b,n; int ans[100005]; void dfs(int x,int k) { if(flag)return; if(x!=1&&k!=0)return; if(x==n+1) { if(k==0) { flag=1; printf("%d",a); for(int i=1;i<=n;i++)printf("%d",ans[i]); } return; } if(flag)return; for(int i=0;i<=9;i++) { ans[x]=i; dfs(x+1,(k*10+i)%b); } } int main() { a=read();b=read();n=read(); dfs(1,a); if(!flag)puts("-1"); return 0; } |
B. Ancient Prophesy
在串中枚举一段，用map统计出现次数
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } char a[100005]; int mp[3000][20][40],ans,pos; int day[]={0,31,28,31,30,31,30,31,31,30,31,30,31}; void check(int l) { string t=""; for(int i=0;i<10;i++) t+=a[i+l]; if(t[2]!='-'||t[5]!='-')return; int d,m,y; for(int i=0;i<10;i++) if(i!=2&&i!=5&&t[i]=='-')return; for(int i=0;i<10;i++) t[i]=t[i]-'0'; d=t[0]*10+t[1]; m=t[3]*10+t[4]; y=t[6]*1000+t[7]*100+t[8]*10+t[9]; if(y<2013||y>2015||m>12||m<1)return; if(d>day[m]||d<1)return; mp[y][m][d]++; if(mp[y][m][d]>ans)ans=mp[y][m][d],pos=l; } int main() { scanf("%s",a+1); int l=strlen(a+1); for(int i=1;i+10-1<=l;i++) check(i); for(int i=0;i<10;i++) printf("%c",a[pos+i]); return 0; } |
C. Balls and Boxes
可以发现，拿来分的那个盒子现在的数量一定是最少的，于是模拟大法
|
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 37 38 39 40 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define inf (ll)1e60 #define mod 1000000007 #define ll long long using namespace std; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n,m; ll a[100005],t=inf; int main() { n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(),t=min(t,a[i]); for(int i=1;i<=n;i++)a[i]-=t; ll s=n*t; while(a[m]) { a[m]--; m--;s++; if(m==0)m=n; } a[m]=s; for(int i=1;i<=n;i++)cout<<a[i]<<' '; return 0; } |
D. Black and White Tree
将两色的结点排序后，依次贪心构造
构造方法很简单
|
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 37 38 39 40 41 42 43 44 45 46 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define mod 1000000007 #define ll long long using namespace std; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n; vector<pa> v[2]; int main() { n=read(); for(int i=1;i<=n;i++) { int c=read(),s=read(); v[c].push_back(make_pair(s,i)); } sort(v[0].begin(),v[0].end()); sort(v[1].begin(),v[1].end()); for(int i=0,j=0;i<v[0].size()&&j<v[1].size();) { int t=min(v[0][i].first,v[1][j].first); printf("%d %d %d\n",v[0][i].second,v[1][j].second,t); v[0][i].first-=t;v[1][j].first-=t; if(v[0][i].first)j++; else if(v[1][j].first)i++; else if(i+1<v[0].size())i++; else j++; } return 0; } |
E. Dividing Kingdom
把点分别按横/纵坐标排序，枚举全排列，直接根据9个值得出直线的位置
然后用线段树check一下
线段树要支持查询左上角一个矩形内的点的个数
按x坐标建立线段树，每个结点放个vector存储结点的y坐标，查询时在对应x坐标的区间内二分
复杂度\(9!*\log{n}^2\)
|
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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define mod 1000000007 #define ll long long using namespace std; int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } int n; pair<int,int>p[100005],q[100005]; vector<int>e,num(9); struct data{ int l,r; vector<int>v; }t[400005]; void build(int k,int l,int r,int x,int y) { t[k].l=l;t[k].r=r; int tmp=0,mid=(l+r)>>1; for(int i=x;i<=y;i++) { t[k].v.push_back(p[i].second); if(p[i].first<=e[mid])tmp=i; } sort(t[k].v.begin(),t[k].v.end()); if(l==r)return; build(k<<1,l,mid,x,tmp); build(k<<1|1,mid+1,r,tmp+1,y); } int query(int k,int x,int y) { if(e[t[k].r]<=x)return upper_bound(t[k].v.begin(),t[k].v.end(),y)-t[k].v.begin(); int tmp=query(k<<1,x,y); if(e[t[k<<1|1].l]<=x)tmp+=query(k<<1|1,x,y); return tmp; } bool check() { int a=num[0]+num[3]+num[6],b=a+num[1]+num[4]+num[7]; int x=p[a-1].first,xx=p[b-1].first; if(p[a].first==x||p[b].first==xx)return 0; int c=num[0]+num[1]+num[2],d=c+num[3]+num[4]+num[5]; int y=q[c-1].first,yy=q[d-1].first; if(q[c].first==y||q[d].first==yy)return 0; if(query(1,x,y)!=num[0])return 0; if(query(1,xx,y)!=num[0]+num[1])return 0; if(query(1,x,yy)!=num[0]+num[3])return 0; if(query(1,xx,yy)!=num[0]+num[1]+num[3]+num[4])return 0; printf("%lf %lf\n%lf %lf ",x+0.5,xx+0.5,y+0.5,yy+0.5); return 1; } int main() { n=read(); for(int i=0;i<n;i++) { int x=read(),y=read(); p[i]=make_pair(x,y); q[i]=make_pair(y,x); e.push_back(x); } sort(e.begin(),e.end()); e.erase(unique(e.begin(),e.end()),e.end()); sort(p,p+n);sort(q,q+n); build(1,0,e.size()-1,0,n-1); for(int i=0;i<9;i++)num[i]=read(); sort(num.begin(),num.end()); do{ if(check())return 0; }while(next_permutation(num.begin(),num.end())); puts("-1"); return 0; } |
Subscribe
计数器 9793879
OI 课件=>
OI 课件=>