春节这几天打了很多场比赛，下面做一个总结和部分题解（没写的不会做）
Codeforces Round #462 (Div. 1)
这是我打的第一场div1，div1和div2有很大的区别。这一次一开始打就卡在了A题，半个多小时才做出来。。
A. A Twisty Movement
题意：给你一个由1和2组成的序列，你可以翻转其中一段，求翻转后的最长不下降子序列。
数据范围：\(1 \leqslant n \leqslant 2000\)
看到这道题之后，可以转换为求枚举一个位置，你要使前面的1和后面的2之和尽可能多。
我们可以把这个序列分成4段，每段长度都可以为0，我们需要把中间两段交换。
这样我们很容易有一个dp的思路，我们要使第一段和第三段的1尽可能多，使第二段和第四段的2尽可能多。
设\(dp[i][j]\)表示当前这一段的最后一位是i，当前在第j段的最大答案
这样转移就很显然了
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
int x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
return x*f;
}
inline ll readll(){
ll x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
return x*f;
}
inline bool chkmax(int &x,int y){return (y>x)?(x=y,1):0;}
const int maxn=2000+10,inf=0x3f3f3f3f;
int a[maxn],sum[maxn],dp[5][maxn];
int main(){
int n=read();
REP(i,1,n) a[i]=read(),sum[i]=sum[i-1]+a[i]-1;
dp[0][0]=0;
REP(i,1,4)
REP(j,0,n)
REP(k,0,j)
if(!(i&1)) chkmax(dp[i][j],dp[i-1][k]+sum[j]-sum[k]);
else chkmax(dp[i][j],dp[i-1][k]+(j-sum[j])-(k-sum[k]));
printf("%d\n",dp[4][n]);
return 0;
}
B. A Determined Cleanup
题意：\(f(x)=q(x)*(x+k)+p\)，其中\(f(x)\)，\(x+k\)与\(q(x)\)都是多项式，给出p与k，求一个合法的\(f(x)\)使得\(f(x)\)的每一位都不超过k
数据范围：\(1 \leqslant p \leqslant 10^{18}\)，\(1 \leqslant k \leqslant 2000\)
式子可以转化\(f(x)\)除以\(x+k\)余数为q，我们考虑一个多项式除以\(x+k\)的过程，发现其实就是一个类似分解成k进制但是每一位要变符号的过程
于是就很好解决了
题目中说无解输出-1，实际上没有无解的情况
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
int x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
return x*f;
}
inline ll readll(){
ll x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
return x*f;
}
const int maxn=200000+10;
ll mod;
int k,n1,n2;
bool work(int *a,int flag,int &n){
int b=flag;
ll p=mod;
while(p!=0){
int tmp=p%k;
if(flag==-1) tmp=(k-tmp)%k;
a[++n]=tmp;
flag*=-1;
p+=flag*tmp;
if(p%k!=0) return 0;
p/=k;
}
if((n&1) && b==-1) return 0;
if(!(n&1) && b==1) return 0;
return 1;
}
int a[maxn],b[maxn];
int main(){
n1=n2=0;
mod=readll(),k=read();
if(work(b,1,n2)){
printf("%d\n",n2);
REP(i,1,n2) printf("%d%c",b[i],i==iend?'\n':' ');
return 0;
}
printf("-1\n");
return 0;
}
C. A Colourful Prospect
这是一道欧拉定理的题目，计算几何需要加强了。
ICM Technex 2018 and Codeforces Round #463 (Div. 1 + Div. 2, combined)
这一场拿小号_ yyc _打的（早知道拿大号打了）
D. Tree
这题一开始被卡题面了，其实就是一个简单的倍增。
（题意过于复杂不想解释）
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
int x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
return x*f;
}
inline ll readll(){
ll x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
return x*f;
}
const int maxn=400000+10;
int v[maxn][20];
ll sum[maxn][20],w[maxn];
int main(){
int q=read(),cnt=1;
ll lst=0;
while(q--){
int ty=read();
ll x=readll(),y=readll();
x^=lst,y^=lst;
if(ty==1){
w[++cnt]=y;
v[cnt][0]=x;
while(v[cnt][0] && w[v[cnt][0]]<y) v[cnt][0]=v[v[cnt][0]][0];
sum[cnt][0]=w[v[cnt][0]];
for(int j=1;v[cnt][j]=v[v[cnt][j-1]][j-1];++j) sum[cnt][j]=sum[cnt][j-1]+sum[v[cnt][j-1]][j-1];
}
else{
ll ans=1;
if(y<w[x]){
lst=0;
printf("0\n");
continue;
}
y-=w[x];
DREP(i,19,0){
if(!v[x][i]) continue;
if(sum[x][i]>y) continue;
y-=sum[x][i];
x=v[x][i];
ans+=(1<<i);
}
lst=ans;
printf("%lld\n",ans);
}
}
return 0;
}
E. Team Work
题意：求\(\sum_{i=1}^{n} C_n^i*i^k\)
数据范围：\(1 \leqslant n \leqslant 10^9\)，\(1 \leqslant k \leqslant 5000\)
首先可以把整数幂转化一下
\[\sum_{i=1}^{n} C_n^i*\sum_{j=0}^{i} S_k^j*C_i^j*j!
\]
将\(C_n^i\)放到后面，把组合数拆开
\[\sum_{i=1}^{n} \sum_{j=0}^{i} S_k^j*\frac {n!} {i!*(n-i)!}*\frac {i!} {j!*(i-j)!}*j!
\]
约分
\[n!*\sum_{i=1}^{n} \sum_{j=0}^{i} S_k^j*\frac {1} {(n-i)!*(i-j)!}
\]
后面一部分转化一下
\[n!*\sum_{i=1}^{n} \sum_{j=0}^{i} S_k^j*C_{n-j}^{n-i}*(n-j)!
\]
交换一下位置
\[n!*\sum_{j=0}^{n} S_k^j*(n-j)!*\sum_{i=j}^{n} C_{n-j}^{n-i}
\]
组合数可以直接转化了
\[\sum_{j=0}^{n} S_k^j*C_n^j*j!*2^{n-j}
\]
这样因为j>k时\(S_k^j=0\)我们可以\(O(k^2)\)处理出答案了
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
int x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
return x*f;
}
inline ll readll(){
ll x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
return x*f;
}
const int maxn=5e3+10,mod=1e9+7;
int S[maxn][maxn],C[maxn],fac[maxn];
int ksm(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*x*res%mod;
x=1ll*x*x%mod;
y>>=1;
}
return res;
}
int main(){
int n=read(),k=read();
S[0][0]=1;
REP(i,1,k){
S[i][0]=0;
S[i][i]=1;
REP(j,1,i-1)
S[i][j]=(S[i-1][j-1]+1ll*j*S[i-1][j]%mod)%mod;
}
C[0]=1;
REP(i,1,min(n,k)) C[i]=1ll*C[i-1]*(n-i+1)%mod*ksm(i,mod-2)%mod;
int ans=0;
fac[0]=1;
REP(i,1,k) fac[i]=1ll*fac[i-1]*i%mod;
REP(i,0,min(n,k)) ans=(ans+1ll*S[k][i]*fac[i]%mod*C[i]%mod*ksm(2,n-i)%mod)%mod;
printf("%d\n",ans);
return 0;
}
Educational Codeforces Round 38 (Rated for Div. 2)
这场我是那小小号zhou8888打的（我为什么有这么多小号）
C. Constructing Tests
题意：对于一个nn的矩阵和一个m，我们设x为每个mm的矩阵都至少有一个0的情况下1最多的个数。
给定q个x，求对于每个x任意一组合法的n和m
数据范围：\(1 \leqslant q \leqslant 100\)，\(1 \leqslant x \leqslant 10^9\)
很容易发现\(x=n^2-(\lfloor \frac {n} {m}\rfloor)^2=(n-\lfloor \frac {n} {m}\rfloor)*(n+\lfloor \frac {n} {m}\rfloor)\)
于是枚举x的约数就行了
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
int x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
return x*f;
}
inline ll readll(){
ll x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
return x*f;
}
int main(){
int T=read();
while(T--){
int x=read(),flag=0;
if(x==0){
printf("1 1\n");
continue;
}
for(int i=1;i*i<=x;++i){
if(x%i) continue;
if(i*i==x) continue;
int y=x/i;
if((i&1)^(y&1)) continue;
int Mid=(y+i)>>1;
int nm=Mid-i;
if(nm>Mid) continue;
int m=Mid/nm;
if(nm!=Mid/m) continue;
printf("%d %d\n",Mid,m);
flag=1;
break;
}
if(!flag) printf("-1\n");
}
return 0;
}
E. Max History
题意：对于一个序列a定义\(f_a\)为
一开始\(f_a=1,M=0\)
对于每个\(2 \leqslant i \leqslant n\)如果$a_M < a_i \(我们让\)f_a+=a_M,M=i\(
给你一个序列，输出这个序列的\)n!\(种排列的\)f_a$总和
数据范围：\(1 \leqslant n \leqslant 10^6\)，\(1 \leqslant a_i \leqslant 10^9\)
首先，肯定是按位考虑，对于每一个数，只有当他之前的数全部小于它时，它的贡献才会被计算
对于每个数，我们可以考虑先把所有比他小的数放进去，然后这个数的位置就确定了，一定是第一个每被放过的位置，剩下的数也随便放
设\(p_i\)为比\(a_i\)小的数的个数，所以答案为
\[\sum_{i=1}^{n} P_n^{p_i}*(n-p_i-1)!=\sum_{i=1}^{n} \frac {n!} {n-p_i}
\]
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
int x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
return x*f;
}
inline ll readll(){
ll x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
return x*f;
}
const int maxn=2e6+10,mod=1e9+7;
int ksm(int x,int y){
int res=1;
while(y){
if(y&1) res=1ll*x*res%mod;
x=1ll*x*x%mod;
y>>=1;
}
return res;
}
int fac[maxn],ifac[maxn];
int a[maxn];
inline void add(int &x,int y){
x+=y;
if(x>=mod) x-=mod;
}
int main(){
int n=read();
fac[0]=1;
REP(i,1,n) fac[i]=1ll*i*fac[i-1]%mod;
ifac[n]=ksm(fac[n],mod-2);
DREP(i,n-1,0) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
int ans=0;
REP(i,1,n) a[i]=read();
sort(a+1,a+n+1);
REP(i,1,n){
int len=1,k=i-1;
while(i+1<=n && a[i]==a[i+1]) len++,++i;
if(i==n)
continue;
add(ans,1ll*fac[n]*a[i]%mod*len%mod*ksm(n-k,mod-2)%mod);
}
printf("%d\n",ans);
return 0;
}
F. Erasing Substrings
题意：给你一个字符串，长度为n，令\(k=\lfloor log_2(n)\rfloor\)，你可以操作k次，第i次操作可以删除一个长度为\(2^{i-1}\)的串，求最后剩下的字典序的串
数据范围：\(1 \leqslant n \leqslant 5000\)
这样的问题我们一般都按位考虑，从第1位到第\((n-2^k+1)\)位,在之前的位最小的情况下，这一位是什么。
我们每一个二进制位上对应的长度都只能选一次，所以我们设\(dp[i]\)代表当前这个字母能够删那些长度，那么我们只要比较第i+pos位的大小就行了，上一个的最小值所在长度的集合，必须选其中至少一个，这样就很好转移了。
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
int x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
return x*f;
}
inline ll readll(){
ll x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
return x*f;
}
const int maxn=5000+10;
bool dp[14][maxn],f[maxn];
char s[maxn];
int main(){
scanf("%s",s+1);
int n=strlen(s+1);
int m=0;
while((1<<m+1)<=n) ++m;
f[0]=1;
REP(k,1,n-(1<<m)+1){
REP(i,0,m) REP(j,0,(1<<m)-1) dp[i][j]=0;
REP(i,0,(1<<m)-1) dp[0][i]=f[i];
REP(i,0,m-1)
REP(j,0,(1<<m)-1)
if(dp[i][j]){
dp[i+1][j]=1;
dp[i+1][j|(1<<i)]=1;
}
int mn=40;
REP(i,0,(1<<m)-1){
if(!dp[m][i]) continue;
mn=min(mn,(int)(s[i+k]-'a'));
}
char c=mn+'a';
putchar(c);
REP(i,0,(1<<m)-1){
f[i]=dp[m][i];
if(c!=s[i+k]) f[i]=0;
}
}
putchar('\n');
return 0;
}
hello xugou
好像难题都没做？？？
Codeforces Round #464 (Div. 2)
经过这场之后我的小号_ yyc _和我的大号同分了。。。
E. Maximize!
题意：维护一个集合，每次加入一个大于集合内所有数的整数。询问这个集合子集的最大值减去平均值的最大值。
数据范围：\(1 \leqslant q \leqslant 5*10^5\)
大力猜结论！！
他的询问我们可以考虑是最大值尽可能大，且使平均值尽可能小
首先，最大值一定取得是最后加进集合中的值，我们可以用反证法来证
然后我们要使平均值尽可能小，我们就每次讲比平均值小的数加进答案中。
由于每次将最大值变大，所以每次加进来一个数后平均值是递增的。
这样我们就可以用一个指针来维护了
#include<bits/stdc++.h>
using namespace std;
#define REP(i,st,ed) for(register int i=st,i##end=ed;i<=i##end;++i)
#define DREP(i,st,ed) for(register int i=st,i##end=ed;i>=i##end;--i)
typedef long long ll;
inline int read(){
int x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
return x*f;
}
inline ll readll(){
ll x;
char c;
int f=1;
while((c=getchar())!='-' && (c>'9' || c<'0'));
if(c=='-') c=getchar(),f=-1;
x=c^'0';
while((c=getchar())>='0' && c<='9') x=(x<<1ll)+(x<<3ll)+(c^'0');
return x*f;
}
const int maxn=5e5+10;
int a[maxn];
double sum[maxn];
int main(){
int q=read(),L=0,R=0;
double lst=0;
double ans=0;
while(q--){
int ty=read();
if(ty==1){
++R;
lst=read();
sum[R]=sum[R-1]+lst;
ans=(sum[L]+lst)/(L+1);
while(L+1<R && sum[L+1]-sum[L]<ans){
++L;
ans=(sum[L]+lst)/(L+1);
}
}
else printf("%.10lf\n",lst-ans);
}
return 0;
}
UOJ Goodbye Dingyou
头一次参加uoj的比赛，难度。。。
Codeforces Round #465 (Div. 2)
C题fst是因为我不知道为什么加了一个特判，然后还判错了。。