这次的比赛真心水，考时估分240，然后各种悠闲乱逛
然后测完T1数组开小了炸成40，T2，T3都没开long long，T2炸成20，T3爆0
掉回1600+的深渊，但是还有CJJ dalao比我更惨，链接
T1
这道题就比较simple了，很显然用数据结构乱优化
貌似有很多种解法：单调队列，堆，线段树等等
我主要就讲一下我考试的时候YY出来的线段树
首先我们发现一个性质：对于n次操作之后，序列就进入循环
然后我们只需要处理处前n次询问就可以O(n)处理了
我们开一个前缀和记录原串中1的个数，然后设一个数组f[i]表示i左边k的长度范围内（包括它自己）一共有几个1（不足k也允许）
然后我们发现将一个数从尾部移到最前面，有两种情况：
如果这个数是0，那么只需要把它自己的f[i]修改成0即可
如果这个数是1，那么只需要把它自己的f[i]就改成1，并且把队头的前k-1项的f[]值加1
然后我们之间把初始数组右移n个长度（前面的为循环做准备)，然后上线段树即可
然而我f数组忘记<<1了，而且那个字符串数组也看错了范围dog！！！
CODE
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100005;
struct segtree
{
int add,s;
}tree[N<<3];
int a[N],f[N<<1],sum[N],ans[N],n,k,q,tot;
char s[N<<1];
inline void read(int &x)
{
x=0; char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
inline void write(int x)
{
if (x/10) write(x/10);
putchar(x%10+'0');
}
inline int max(int a,int b)
{
return a>b?a:b;
}
inline void up(int root)
{
tree[root].s=max(tree[root<<1].s,tree[root<<1|1].s);
}
inline void down(int root)
{
if (tree[root].add)
{
tree[root<<1].add+=tree[root].add;
tree[root<<1|1].add+=tree[root].add;
tree[root<<1].s+=tree[root].add;
tree[root<<1|1].s+=tree[root].add;
tree[root].add=0;
}
}
inline void build(int root,int l,int r)
{
if (l==r)
{
tree[root].s=f[l];
return;
}
int mid=l+r>>1;
build(root<<1,l,mid); build(root<<1|1,mid+1,r);
up(root);
}
inline void updata(int root,int l,int r,int id)
{
if (l==r)
{
tree[root].s=0;
return;
}
int mid=l+r>>1;
down(root);
if (id<=mid) updata(root<<1,l,mid,id); else updata(root<<1|1,mid+1,r,id);
up(root);
}
inline void modify(int root,int l,int r,int beg,int end)
{
if (l>=beg&&r<=end)
{
tree[root].s+=1; tree[root].add+=1;
return;
}
int mid=l+r>>1;
down(root);
if (beg<=mid) modify(root<<1,l,mid,beg,end);
if (end>mid) modify(root<<1|1,mid+1,r,beg,end);
up(root);
}
int main()
{
//freopen("A.in","r",stdin); freopen("A.out","w",stdout);
register int i;
read(n); read(k); read(q);
for (i=1;i<=n;++i)
{
read(a[i]); sum[i]=sum[i-1]+a[i];
if (i>=k) f[i+n]=sum[i]-sum[i-k]; else f[i+n]=sum[i];
}
build(1,1,n<<1);
ans[0]=tree[1].s;
for (i=1;i<=n;++i)
{
updata(1,1,n<<1,(n<<1)-i+1);
if (a[n-i+1]) modify(1,1,n<<1,n-i+1,n-i+k);
ans[i]=tree[1].s;
}
for (scanf("%s",s+1),i=1;i<=q;++i)
if (s[i]=='?') write(ans[tot]),putchar('\n'); else { if (++tot==n) tot=0; }
return 0;
}
T2
这题意一看就是暴力数据结构，然而我没开long long
我们通过观察发现2操作满足一个很凶猛的性质：前面的操作不会影响后面的操作
因此我们可以从前往后推一下，对于所有的操作2，将它操作的区间中的所有操作的次数+=目前这个操作的次数（默认为1）
然后最后我们得到了所有操作的次数，然后对于操作1上线段树 or 树状数组+差分即可
线段树CODE
#include<cstdio>
using namespace std;
typedef long long LL;
const LL N=100005,mod=1e9+7;
struct time_segtree
{
LL add[N<<2],sum[N<<2];
inline void up(LL root)
{
sum[root]=(sum[root<<1]+sum[root<<1|1])%mod;
}
inline void down(LL root,LL l,LL r)
{
if (add[root])
{
add[root<<1]=(add[root<<1]+add[root])%mod;
add[root<<1|1]=(add[root<<1|1]+add[root])%mod;
sum[root<<1]=(sum[root<<1]+add[root]*l)%mod;
sum[root<<1|1]=(sum[root<<1|1]+add[root]*r)%mod;
add[root]=0;
}
}
inline void modify(LL root,LL l,LL r,LL beg,LL end,LL k)
{
if (l>=beg&&r<=end)
{
sum[root]=(sum[root]+k*(r-l+1))%mod;
add[root]=(add[root]+k)%mod;
return;
}
LL mid=l+r>>1;
down(root,mid-l+1,r-mid);
if (beg<=mid) modify(root<<1,l,mid,beg,end,k);
if (end>mid) modify(root<<1|1,mid+1,r,beg,end,k);
up(root);
}
inline LL query(LL root,LL l,LL r,LL id)
{
if (l==r) return sum[root];
LL mid=l+r>>1;
down(root,mid-l+1,r-mid);
if (id<=mid) return query(root<<1,l,mid,id); else return query(root<<1|1,mid+1,r,id);
}
}T;
struct ans_segtree
{
LL add[N<<2],sum[N<<2];
inline void up(LL root)
{
sum[root]=(sum[root<<1]+sum[root<<1|1])%mod;
}
inline void down(LL root,LL l,LL r)
{
if (add[root])
{
add[root<<1]=(add[root<<1]+add[root])%mod;
add[root<<1|1]=(add[root<<1|1]+add[root])%mod;
sum[root<<1]=(sum[root<<1]+add[root]*l)%mod;
sum[root<<1|1]=(sum[root<<1|1]+add[root]*r)%mod;
add[root]=0;
}
}
inline void modify(LL root,LL l,LL r,LL beg,LL end,LL k)
{
if (l>=beg&&r<=end)
{
sum[root]=(sum[root]+k*(r-l+1))%mod;
add[root]=(add[root]+k)%mod;
return;
}
LL mid=l+r>>1;
down(root,mid-l+1,r-mid);
if (beg<=mid) modify(root<<1,l,mid,beg,end,k);
if (end>mid) modify(root<<1|1,mid+1,r,beg,end,k);
up(root);
}
inline LL query(LL root,LL l,LL r,LL id)
{
if (l==r) return sum[root];
LL mid=l+r>>1;
down(root,mid-l+1,r-mid);
if (id<=mid) return query(root<<1,l,mid,id); else return query(root<<1|1,mid+1,r,id);
}
}A;
struct data
{
LL opt,x,y;
}q[N];
LL n,m;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(LL &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void write(LL x)
{
if (x/10) write(x/10);
putchar(x%10+'0');
}
int main()
{
//freopen("B.in","r",stdin); freopen("B.out","w",stdout);
register LL i;
read(n); read(m);
for (i=1;i<=m;++i)
read(q[i].opt),read(q[i].x),read(q[i].y);
for (i=m;i>=1;--i)
{
T.modify(1,1,m,i,i,1);
if (q[i].opt==2) { LL x=T.query(1,1,m,i); T.modify(1,1,m,q[i].x,q[i].y,x); }
}
for (i=1;i<=m;++i)
if (q[i].opt==1) { LL x=T.query(1,1,m,i); A.modify(1,1,n,q[i].x,q[i].y,x); }
for (i=1;i<=n;++i)
write(A.query(1,1,n,i)),putchar(' ');
return 0;
}
T3
比较玄学的卢卡斯定理乱推
反正我对这种数学的东西没什么兴趣，还是打打暴力好了
这里的暴力也比较有技巧，我们搞一下每一个点第x天的权值，记录下来，因为既可以用来推后面的，也可以用来O(1)求答案
40ptsCODE
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const LL N=1005;
struct edge
{
LL to,next;
}e[N<<1];
LL head[N],w[N][N],a[N],n,q,x,y,root,cnt,m;
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(LL &x)
{
x=0; char ch=tc();
while (ch<'0'||ch>'9') ch=tc();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=tc();
}
inline void write(LL x)
{
if (x/10) write(x/10);
putchar(x%10+'0');
}
inline void add(LL x,LL y)
{
e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;
}
inline LL max(LL a,LL b)
{
return a>b?a:b;
}
inline void DFS(LL now,LL fa)
{
bool flag=1; register LL i,j;
for (i=head[now];i!=-1;i=e[i].next)
if (e[i].to!=fa)
{
flag=0;
DFS(e[i].to,now);
}
if (flag) for (i=1;i<=m;++i) w[now][i]=w[now][0]; else
{
for (i=1;i<=m;++i)
for (w[now][i]=w[now][i-1],j=head[now];j!=-1;j=e[j].next)
if (e[j].to!=fa) w[now][i]^=w[e[j].to][i];
}
}
int main()
{
//freopen("C.in","r",stdin); freopen("C.out","w",stdout);
register LL i;
memset(head,-1,sizeof(head));
memset(e,-1,sizeof(e));
read(n); read(q);
for (i=1;i<n;++i)
read(x),read(y),add(x,y),add(y,x);
for (i=0;i<n;++i)
read(w[i][0]);
for (i=1;i<=q;++i)
read(a[i]),m=max(m,a[i]);
DFS(root,-1);
for (i=1;i<=q;++i)
write(w[root][a[i]]),putchar('\n');
return 0;
}