Educational Codeforces Round 63 (Div.2)

A.若存在解则一定存在某个i使得a[i]>a[i+1]，翻转它即可。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 6 typedef long long ll;
 7 using namespace std;
 8 
 9 const int N=300010;
10 int n;
11 char s[N];
12 
13 int main(){
14     scanf("%d%s",&n,s+1);
15     rep(i,1,n-1) if (s[i]>s[i+1]){ printf("YES
%d %d
",i,i+1); return 0; }
16     puts("NO");
17     return 0;
18 }

B.看前n-10个中8的个数是否够对方删即可，不会证明。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 6 typedef long long ll;
 7 using namespace std;
 8 
 9 const int N=300010;
10 int n;
11 char s[N];
12 
13 int main(){
14     scanf("%d%s",&n,s+1);
15     rep(i,1,n-1) if (s[i]>s[i+1]){ printf("YES
%d %d
",i,i+1); return 0; }
16     puts("NO");
17     return 0;
18 }

C.第一次响铃一定是x[1]时，然后只要找到一个所有y的gcd即可。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 6 typedef long long ll;
 7 using namespace std;
 8 
 9 const int N=300010;
10 int n,m;
11 ll d,p,x[N];
12 
13 ll gcd(ll a,ll b){ return b ? gcd(b,a%b) : a; }
14 
15 int main(){
16     scanf("%d%d",&n,&m);
17     rep(i,1,n) cin>>x[i]; ll d=x[2]-x[1];
18     rep(i,3,n) d=gcd(d,x[i]-x[i-1]);
19     rep(i,1,m){
20         cin>>p;
21         if (d%p==0){ cout<<"YES
"<<x[1]<<' '<<i<<endl; return 0; }
22     }
23     puts("NO");
24     return 0;
25 }

D.f[i][0/1/2]表示前i个数，i在选择*x的那个区间之前/之中/之后，的最大子段和。转移显然。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 6 typedef long long ll;
 7 using namespace std;
 8 
 9 const int N=300010;
10 int n,m;
11 ll d,p,x[N];
12 
13 ll gcd(ll a,ll b){ return b ? gcd(b,a%b) : a; }
14 
15 int main(){
16     scanf("%d%d",&n,&m);
17     rep(i,1,n) cin>>x[i]; ll d=x[2]-x[1];
18     rep(i,3,n) d=gcd(d,x[i]-x[i-1]);
19     rep(i,1,m){
20         cin>>p;
21         if (d%p==0){ cout<<"YES
"<<x[1]<<' '<<i<<endl; return 0; }
22     }
23     puts("NO");
24     return 0;
25 }

E.拉格朗日插值模板题，用11次询问即可确定这个多项式。把多项式插出来，再暴力枚举x0每次O(11)带入多项式计算结果是否为0即可。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #define rep(i,l,r) for (int i=(l); i<=(r); i++)
 6 typedef long long ll;
 7 using namespace std;
 8 
 9 const int N=110,mod=1e6+3;
10 int y[N],g[N],gg[N],f[N];
11 
12 int ksm(int a,int b){
13     int res=1;
14     for (; b; a=1ll*a*a%mod,b>>=1)
15         if (b & 1) res=1ll*res*a%mod;
16     return res;
17 }
18 
19 int que(int x){
20     cout<<'?'<<' '<<x<<endl; cin>>x;
21     if (x==-1) exit(0); return x;
22 }
23 
24 int F(int x){
25     int s=1,res=0;
26     rep(i,0,10) res=(res+1ll*f[i]*s%mod+mod)%mod,s=1ll*s*x%mod;
27     return res;
28 }
29 
30 int main(){
31     rep(i,0,10) y[i]=que(i);
32     rep(k,0,10){
33         g[0]=1; int s=1;
34         rep(j,1,10) g[j]=0;
35         rep(j,0,10) if (j!=k){
36             rep(i,0,10) gg[i]=g[i];
37             for (int i=9; ~i; i--) g[i+1]=g[i]; g[0]=0;
38             rep(i,0,10) g[i]=(g[i]-1ll*gg[i]*j%mod+mod)%mod;
39             s=1ll*s*(k-j+mod)%mod;
40         }
41         rep(j,0,10) f[j]=(f[j]+1ll*y[k]*g[j]%mod*ksm(s,mod-2)%mod+mod)%mod;
42     }
43     rep(p,0,mod-1) if (!F(p)){ cout<<'!'<<' '<<p<<endl; return 0; }
44     cout<<'!'<<' '<<-1<<endl;
45     return 0;
46 }