GDOI模拟赛Round 1
数据结构
题目描述：给出一个长度为\(n\)的序列，支持两种操作：
1、对某段区间都加上一个数
2、给出\(p、k\),求下面表示式对\((10^9+7)\)取模
\[\sum_{i=1}^{n} a_i \times max(0, k-|i-p|)
\]
\]
solution
维护某段区间 第一个数乘1+ 第二个数乘2+ …… +第\(n\)个数乘\(n\)是线段树的经典题型，把问题拆成两部分\((p-k, i),(i, p+k)\),注意一下边界就可以了。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
const int maxn=int(1e5)+100;
const int mod=int(1e9)+7;
struct data
{
int x, y;
LL value;
void init(int _x, int _y, LL _value)
{
x=_x;
y=_y;
value=_value;
}
};
int n, m;
LL tree[maxn*4][3];
LL add[maxn*4];
data dat;
void down(int cur, int L, int R)
{
int mid=(L+R)>>1;
tree[cur<<1][2]=(tree[cur<<1][2]+add[cur]*(mid-L+1)%mod)%mod;
tree[cur<<1 | 1][2]=(tree[cur<<1 | 1][2]+add[cur]*(R-mid)%mod)%mod;
LL tmp=add[cur]*(((LL(1+mid-L+1))*(mid-L+1)/2)%mod)%mod;
tree[cur<<1][0]=(tree[cur<<1][0]+tmp)%mod;
tree[cur<<1][1]=(tree[cur<<1][1]+tmp)%mod;
tmp=add[cur]*(((LL(1+R-mid))*(R-mid)/2)%mod)%mod;
tree[cur<<1 | 1][0]=(tree[cur<<1 | 1][0]+tmp)%mod;
tree[cur<<1 | 1][1]=(tree[cur<<1 | 1][1]+tmp)%mod;
add[cur<<1]=(add[cur<<1]+add[cur])%mod;
add[cur<<1 | 1]=(add[cur<<1 | 1]+add[cur])%mod;
add[cur]=0;
}
void update(int cur, int L, int R)
{
if (L>dat.y || R<dat.x) return;
if (dat.x<=L && R<=dat.y)
{
tree[cur][2]=(tree[cur][2]+dat.value*(R-L+1)%mod)%mod;
LL tmp=dat.value*(((LL(1+R-L+1))*(R-L+1)/2)%mod)%mod;
tree[cur][0]=(tree[cur][0]+tmp)%mod;
tree[cur][1]=(tree[cur][1]+tmp)%mod;
add[cur]=(add[cur]+dat.value)%mod;
return;
}
int mid=(L+R)>>1;
if (add[cur]!=0) down(cur, L, R);
update(cur<<1, L, mid);
update(cur<<1 | 1, mid+1, R);
tree[cur][2]=(tree[cur<<1][2]+tree[cur<<1 | 1][2])%mod;
tree[cur][0]=(tree[cur<<1][0]+tree[cur<<1 | 1][0]+tree[cur<<1 | 1][2]*(mid-L+1)%mod)%mod;
tree[cur][1]=(tree[cur<<1 | 1][1]+tree[cur<<1][1]+tree[cur<<1][2]*(R-mid)%mod)%mod;
}
LL ask(int cur, int L, int R)
{
if (L>dat.y || R<dat.x) return 0;
if (dat.x<=L && R<=dat.y)
{
if (dat.value==2) return tree[cur][2];
if (dat.value==0) return ((tree[cur][0]+tree[cur][2]*(L-dat.x)%mod)%mod);
return ((tree[cur][1]+tree[cur][2]*(dat.y-R)%mod)%mod);
}
int mid=(L+R)>>1;
if (add[cur]!=0) down(cur, L, R);
return ((ask(cur<<1, L, mid)+ask(cur<<1 | 1, mid+1, R))%mod);
}
void init()
{
scanf("%d%d", &n, &m);
for (int i=1; i<=n; ++i)
{
int value;
scanf("%d", &value);
dat.init(i, i, value);
update(1, 1, n);
}
}
void solve()
{
for (int i=1; i<=m; ++i)
{
int nid, p, k;
scanf("%d", &nid);
if (nid & 1)
{
scanf("%d%d", &p, &k);
if (k==0)
{
printf("0\n");
continue;
}
dat.init(max(p-k+1, 1), p, 0);
LL ans=ask(1, 1, n);
dat.init(p, min(p+k-1, n), 1);
ans=(ans+ask(1, 1, n)+mod)%mod;
if (p-k+1<=0)
{
dat.init(1, p, 2);
ans=(ans+ask(1, 1, n)*(k-p)%mod+mod)%mod;
}
if (p+k-1>n)
{
dat.init(p, n, 2);
ans=(ans+ask(1, 1, n)*(p+k-1-n)%mod+mod)%mod;
}
dat.init(p, p, 2);
ans=(ans-ask(1, 1, n)*k%mod+mod)%mod;
while (ans<0) ans+=mod;
printf("%I64d\n", ans);
}
else
{
scanf("%d%d%I64d", &dat.x, &dat.y, &dat.value);
update(1, 1, n);
}
}
}
int main()
{
freopen("gdds.in", "r", stdin);
freopen("gdds.out", "w", stdout);
init();
solve();
return 0;
}
树之谜题
原题TopCoder
题目描述：有一棵\(n\)个结点的树，根的位置放了一个红色标记，其它一些结点放了黑色标记。每当一个有标记的结点，当它相邻某个结点没有标记，则可以把当前标记移到那个没有标记的结点，问红色标记能到那些点。
solution
我从这题中领悟到了爆搜的魅力。首先把这棵树看成是无根树，预处理出当\(i\)的父亲为\(j\)时，\(i\)的子树的结点数。然后再看回是有根树，求出每个结点的子树的黑色结点数。爆搜的时候还是把它看做无根树。
然后以\([prev][cur][sum]\)为状态，表示当前红色标记在\(cur\),且\(cur\)的父亲是\(prev\)，\(cur\)的子树中黑色结点数为\(sum\).
如果红色部分的黑色结点数\((total-sum)\)小于红色部分的结点数，那么搜索\([cur][prev][total-sum]\)
然后枚举\(cur\)的儿子\(i\),枚举分配\(j\)个黑色结点给它，能这样分配的条件是1、\(j\)小于\(i\)子树的结点数，2、\((sum-j)\)个黑色结点能塞进\(cur\)的其它儿子那里，即\((sum-j)\)小于\(cur\)其它儿子的子树结点数总和，满足上述条件就可以搜索\([cur][i][j]\).
因为有用状态不多，所以不会爆空间
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <set>
#include <map>
using namespace std;
const int maxn=310;
struct LINK
{
int id, next;
};
struct data
{
int cur, prev, sum;
};
int n;
int now, qsize;
int black[maxn], ans[maxn];
int h[maxn], size[maxn][maxn], sum[maxn];
bool vis[maxn][maxn][maxn];
data q[maxn*maxn*5];
LINK t[maxn*2];
void join(int u, int v)
{
t[now].id=v; t[now].next=h[u]; h[u]=now++;
t[now].id=u; t[now].next=h[v]; h[v]=now++;
}
void init()
{
scanf("%d", &n);
for (int i=0; i<n; ++i) h[i]=-1;
for (int i=0; i<n; ++i)
{
int v;
scanf("%d", &v);
if (i==0) continue;
join(i, v);
}
for (int i=0; i<n; ++i)
{
int flag;
scanf("%d", &flag);
if (i==0) continue;
black[i]=flag;
}
}
int calc_size(int prev, int cur)
{
if (size[prev][cur]>0) return size[prev][cur];
size[prev][cur]=1;
for (int i=h[cur]; i>-1; i=t[i].next)
if (t[i].id!=prev)
size[prev][cur]+=calc_size(cur, t[i].id);
return size[prev][cur];
}
int calc_s(int prev, int cur)
{
sum[cur]=black[cur];
for (int i=h[cur]; i>-1; i=t[i].next)
if (t[i].id!=prev)
sum[cur]+=calc_s(cur, t[i].id);
return sum[cur];
}
void insert(int prev, int cur, int sum)
{
if (vis[prev][cur][sum]) return;
vis[prev][cur][sum]=true;
q[++qsize].prev=prev;
q[qsize].cur=cur;
q[qsize].sum=sum;
}
void solve()
{
for (int i=0; i<n; ++i)
for (int j=h[i]; j>-1; j=t[j].next)
calc_size(i, t[j].id);
calc_s(-1, 0);
qsize=0;
for (int i=h[0]; i>-1; i=t[i].next)
if (size[0][t[i].id]>sum[t[i].id])
insert(0, t[i].id, sum[t[i].id]);
int total=sum[0];
ans[0]=true;
for (int i=1; i<=qsize; ++i)
{
int prev=q[i].prev;
int cur=q[i].cur;
int s=q[i].sum;
ans[cur]=true;
if (total-s<size[cur][prev])
insert(cur, prev, total-s);
int sn=0;
for (int j=h[cur]; j>-1; j=t[j].next)
if (t[j].id!=prev) sn+=size[cur][t[j].id];
for (int j=h[cur]; j>-1; j=t[j].next)
if (t[j].id!=prev)
{
for (int k=0; k<=s && k<size[cur][t[j].id]; ++k)
if (sn-size[cur][t[j].id]>=s-k)
insert(cur, t[j].id, k);
}
}
}
int main()
{
freopen("puzzle.in", "r", stdin);
freopen("puzzle.out", "w", stdout);
init();
solve();
for (int i=0; i<n; ++i)
printf("%d ", ans[i]);
return 0;
}
不公平的比赛
题目描述：M和C决定来场摔跤比赛。当然不是他们亲自对战，而是他们各派出\(n\)名勇士进行对战，不妨用\(M_i\)，表示M的标号为\(i\)的勇士，同样的\(C_i\)表示C的标号为\(i\)的勇士，其中对勇士的标号从\(0\)开始。
比赛分\(n\)场进行。
第\(i\)场比赛，先是\(M_{i-1}\)和\(C_0\)对战。如果打成平局，那么进行下一局比赛，由\(M_i\)和\(C_1\)对战。如果还是打成平局，那么再进行下一局比赛，由\(M_{i+1}\)和\(C_2\)对战，以此类推，直到决出胜负为止，也就是说，如果前$j (1 \leq j < n) \(局都是平局，则下一局将由\)M_{ (i+j-1) % n}\(和\)C_j\(对决。如果一直打到\)M_{i-2}\(和\)C_{n-1}\(都没有分出胜负，那么第\)i$场比赛平。
胜负有对战双方的力量值决定。
求出M和C各赢了多少场，以及一共进行了多少局比赛。
solution
其实就是以\(M\)为被匹配串，\(C\)为标准串，求以第\(i\)位为开头的后缀的最长公共前缀。用扩展KMP可以轻松解决。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <set>
#include <map>
using namespace std;
const int maxn=int(1e5)+100;
typedef long long LL;
int n;
int st[maxn*2];
int str[maxn];
int ans[maxn], next[maxn];
LL s;
int sm, sc;
void init()
{
scanf("%d", &n);
for (int i=0; i<n; ++i) scanf("%d", &st[i]);
for (int i=0; i<n; ++i) scanf("%d", &str[i]);
for (int i=0; i<n; ++i) st[i+n]=st[i];
}
void solve()
{
next[0]=n;
for (int i=0; i<n; ++i)
if (str[1+i]==str[i]) ++next[1];
else break;
for (int i=2, p=1, maxid=next[1]+1; i<n; ++i)
{
if (next[i-p]+i<maxid) next[i]=next[i-p];
else
{
next[i]=max(maxid-i, 0);
while (i+next[i]<n && str[next[i]]==str[i+next[i]]) ++next[i];
if (i+next[i]>=maxid)
{
maxid=i+next[i];
p=i;
}
}
}
for (int i=0; i<n; ++i)
if (st[i]==str[i]) ++ans[0];
else break;
for (int i=1, p=0, maxid=ans[0]; i<n; ++i)
{
if (next[i-p]+i<maxid) ans[i]=next[i-p];
else
{
ans[i]=max(maxid-i, 0);
while (ans[i]<n && str[ans[i]]==st[i+ans[i]]) ++ans[i];
if (i+ans[i]>=maxid)
{
maxid=i+ans[i];
p=i;
}
}
}
for (int i=0; i<n; ++i)
{
if (ans[i]==n)
{
s+=n;
continue;
}
s+=ans[i]+1;
if (st[i+ans[i]]>str[ans[i]]) ++sm;
else ++sc;
}
printf("%d %d %I64d\n", sm, sc, s);
}
int main()
{
freopen("wrestling.in", "r", stdin);
freopen("wrestling.out", "w", stdout);
init();
solve();
return 0;
}