https://codeforces.com/contest/1142
A. The Beatles
A题随便写写就行了(
直接暴力枚举间距就好了。
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
| #include<bits/stdc++.h> using namespace std; #define int long long void read(int &x) { x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; } void print(int x) { if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar(x%10+48); } void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define pii pair<int,int > #define vec vector<int > #define pb push_back #define mp make_pair #define fr first #define sc second #define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) const int maxn = 1e6+10; const int inf = 1e9; const lf eps = 1e-8; const int mod = 1e9+7; int n,k,a,b,p[5]; signed main() { read(n),read(k),read(a),read(b); p[1]=a+b,p[2]=a+k-b,p[3]=k-a+b,p[4]=k-a+k-b; for(int i=1;i<=4;i++) if(p[i]>k) p[i]-=k; int ans1=1e18,ans2=0; for(int i=1;i<=n;i++) for(int j=1;j<=4;j++) { int t=n*k/__gcd(n*k,p[j]); ans1=min(ans1,t),ans2=max(ans2,t); if(p[j]+k<=n*k) p[j]+=k; } printf("%lld %lld\n",ans1,ans2); return 0; }
|
B. Lynyrd Skynyrd
首先处理出$f_i$表示$i$后面最靠近的能匹配位置是哪个。
那么直接对这个数组倍增然后每次暴力判断就好了。
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
| #include<bits/stdc++.h> using namespace std; void read(int &x) { x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; } void print(int x) { if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar(x%10+48); } void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define pii pair<int,int > #define vec vector<int > #define pb push_back #define mp make_pair #define fr first #define sc second #define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) const int maxn = 1e6+10; const int inf = 1e9; const lf eps = 1e-8; const int mod = 1e9+7; int p[maxn],a[maxn],f[maxn][20],t[maxn],n,m,q,rev[maxn],r[maxn]; int main() { read(n),read(m),read(q); for(int i=1;i<=n;i++) read(p[i]),rev[p[i]]=i; for(int i=1;i<=m;i++) read(a[i]); for(int i=1;i<=m;i++) { if(a[i]==p[1]) f[i][0]=t[n]; else f[i][0]=t[rev[a[i]]-1]; t[rev[a[i]]]=i; } for(int i=1;i<=m;i++) for(int j=1;j<20;j++) f[i][j]=f[f[i][j-1]][j-1]; for(int i=1;i<=m;i++) { int d=n-1,p=i; for(int j=0;j<20;j++) if(d&(1<<j)) d-=1<<j,p=f[p][j]; r[i]=max(r[i-1],p); } for(int i=1;i<=q;i++) { int x,y;read(x),read(y); if(r[y]>=x) putchar('1'); else putchar('0'); }puts(""); return 0; }
|
C. U2
挺神仙的…反正我是参考了题解
注意到抛物线的式子:$y=x^2+bx+c$,移下项就是$y-x^2=bx+c$。
那么把每个点$(x,y)$改成$(x,y-x^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
| #include<bits/stdc++.h> using namespace std; #define int long long void read(int &x) { x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; } void print(int x) { if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar(x%10+48); } void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define pii pair<int,int > #define vec vector<int > #define pb push_back #define mp make_pair #define fr first #define sc second #define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) const int maxn = 1e6+10; const int inf = 1e9; const lf eps = 1e-8; const int mod = 1e9+7; struct P { int x,y; P operator - (const P &a) {return (P){x-a.x,y-a.y};} int operator * (const P &a) {return x*a.y-y*a.x;} }a[maxn],sta[maxn]; int n,top; int cmp(P x,P y) {return x.x==y.x?x.y>y.y:x.x<y.x;} signed main() { read(n); for(int i=1;i<=n;i++) read(a[i].x),read(a[i].y),a[i].y-=a[i].x*a[i].x; sort(a+1,a+n+1,cmp);a[0].x=1e18; for(int i=1;i<=n;i++) { if(a[i].x==a[i-1].x) continue; if(top<=1) sta[++top]=a[i]; else { while(top>1&&(sta[top-1]-sta[top])*(a[i]-sta[top])<=0) top--; sta[++top]=a[i]; } }write(top-1); return 0; }
|
D. Foreigner
假设我们现在有一个合法的数$x$,他的排名为$r \pmod {11}$。
那么我们现在考虑求出往$x$后面添一个$0$,排名会变为多少(注意这里说的排名都是模$11$意义下)。
首先如果我们按题意模拟来生成这个数列,可以发现这个数列就是升序的。
那么我们现在就是想统计$[1,x]$会生成多少个合法的数。
注意到排名模$11$分别为$0-10$的数共计会生成$1+2+..+10+0=55=11\times 5$个数,所以这些数其实是可以忽略掉的。
那么其实有贡献的就只有排名为$0\sim r-1$的数会贡献,这部分一共有$\frac{r(r-1)}{2}$个数。
注意到排名为$0$(此处不算取模)不是一个合法的数所以还要减一。
所以$10x$的排名就是$\frac{r(r-1)}{2}-1\pmod {11}$。
反之,对于任意$x$,排名就是:
那么直接$dp$算答案,设$f_{i,j}$表示当前排名为$j$,从第$i$位开始往后接最多能接多少个数字。
随便转移一下就好了。
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
| #include<bits/stdc++.h> using namespace std; void read(int &x) { x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; } void print(int x) { if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar(x%10+48); } void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define pii pair<int,int > #define vec vector<int > #define pb push_back #define mp make_pair #define fr first #define sc second #define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) const int maxn = 1e6+10; const int inf = 1e9; const lf eps = 1e-8; const int mod = 1e9+7; #define ll long long char s[maxn]; int n,f[maxn][12]; ll ans; int main() { scanf("%s",s+1);n=strlen(s+1); for(int i=n;i;i--) { int t=s[i]-'0'; for(int j=0;j<=10;j++) if(t>=j) f[i][j]=0; else f[i][j]=f[i+1][(j*(j-1)/2+t+10)%11]+1; if(t) ans+=f[i+1][t]+1; }printf("%lld\n",ans); return 0; }
|
E. Pink Floyd
首先考虑没有粉色的边怎么做,我们硬点一个答案$x$,然后询问一个没问过的$y$,如果是$x\to y$就不管,否则把答案换成$y$即可。
如果有粉色的边,我们首先把粉色的边搞出一个图来,然后搞出若干个$\rm dfs$树,那么在这个树上就只有树边和返祖边,也就是指向祖先的边。
我们搞出一个集合$s$,表示待选的答案集合,我们一开始把每个根丢进去,然后每次拿出两个点,询问一下,假设$x\to y$,那么我们把$y$从集合和树上都删掉,然后把$y$的儿子加进集合,直到集合只剩一个点。
分析一下这样的正确性,我们每次选出来的点$x,y$,$x,y$之间必然不存在粉色的边,因为连向儿子的边儿子还没加进集合,连向祖先的边也一定被删掉了,所以一定不存在粉色的边。
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
| #include<bits/stdc++.h> using namespace std; void read(int &x) { x=0;int f=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f; } void print(int x) { if(x<0) putchar('-'),x=-x; if(!x) return ;print(x/10),putchar(x%10+48); } void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');} #define lf double #define pii pair<int,int > #define vec vector<int > #define pb push_back #define mp make_pair #define fr first #define sc second #define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++) const int maxn = 1e6+10; const int inf = 1e9; const lf eps = 1e-8; const int mod = 1e9+7; int n,m,vis[maxn],in[maxn],d[maxn],sta[maxn],top; vector<int > e[maxn],t[maxn]; void dfs(int x) { vis[x]=in[x]=1; for(auto v:e[x]) { if(!in[v]) t[x].pb(v),d[v]++; if(!vis[v]) dfs(v); }in[x]=0; } int main() { read(n),read(m); for(int i=1,x,y;i<=m;i++) read(x),read(y),e[x].pb(y); for(int i=1;i<=n;i++) if(!vis[i]) dfs(i); for(int i=1;i<=n;i++) if(!d[i]) sta[++top]=i; while(top>1) { int x=sta[top--],y=sta[top--],op; printf("? %d %d\n",x,y);fflush(stdout);read(op); if(!op) swap(x,y);sta[++top]=x;for(auto v:t[y]) if(!(--d[v])) sta[++top]=v; }printf("! ");write(sta[top]);fflush(stdout); return 0; }
|