第一题：
给出一个长度不超过100只包含'B'和'R'的字符串，将其无限重复下去。
比如，BBRB则会形成
BBRBBBRBBBRB
现在给出一个区间[l,r]询问该区间内有多少个字符'B'(区间下标从1开始) [1<=l,r<=1e18]
解： 没想到第一题这么水。直接前缀和+mod就可以了，再判一下边界。注意1e18不需要高精度。long long 有9*10^18.
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 105
#define ll long long
using namespace std;
char c[maxn];
ll len,ans,l,r,sum[maxn];
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%s",c+);
cin>>l>>r;
len=strlen(c+);
for (int i=;i<=len;i++)
{
sum[i]=sum[i-];
if (c[i]=='B') sum[i]++;
}
ans=(r/len)*sum[len]+sum[r%len]-(l/len)*sum[len]-sum[l%len];
if ((l%len==&&c[len]=='B')||c[l%len]=='B') ans++;
printf("%I64d",ans);
return ;
}
第二题：（codeforces 580D:Kefa and Dishes）
我们要从n种食物选m个出来，安排一个顺序吃掉它（们），每种食物有个美味值ai，然后我们有k个规则，每个规则有 xi, yi 和 ci三个数，如果吃完第xi种食物接下来马上吃第yi种食物，第j种食物的美味值会增加ci。每种食物至多吃一个，求美味值最大的和是多少？
n,m<=18,ai,ci<=10^9
解：
看到这么小的数据范围就是状压dp了。想到是第一次自己写，还是很欣慰的得了50%。我的方法是f[i][j]表示选了 i 个的状态 j 。写转移方程的时候遇到了问题，不能表示上一个选的是什么（而从这一点出发可以想到换第一维的表示，可以换为last取的食物，于是我与标答失之交臂）所以把 f 写了一个结构体，存下美味值和上一次选的食物。然后就是转移方程，我先循环m，然后枚举所有状态，判断该状态是否符合只取了当前个食物，然后枚举n，加入下一个状态。
还是不知道为什么WA了5个点，等写完博客来看看。
50分代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define M 300000
#define maxn 20
#define ll long long
using namespace std;
int n,m,k,ma;
ll v[maxn];
struct pp{
ll tastyy;
int chos;
};
pp f[maxn][M];
ll ad[maxn][maxn];
bool pd(int x,int y)
{
int sum=;
for (int i=;i<n;i++)
{
if ((<<i)&x) sum++;
if (sum>y-) return false;
}
if (sum==y-) return true;
else return false;
}
int main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for (int i=;i<=n;i++)
scanf("%I64d",&v[i]);
for (int i=;i<=k;i++)
{
int x,y;
ll z;
scanf("%d%d%I64d",&x,&y,&z);
ad[x][y]=z;
}
for (int i=;i<=m;i++)
{
f[i][].tastyy=-;
ma=(ma|(<<(n-i)));//n-i
}
for (int i=;i<=n;i++)
{
int x=(<<(i-));// not f[1][i]
f[][x].tastyy=v[i];
f[][x].chos=i;
}
for (int i=;i<=m;i++)
{
for (int j=;j<=ma;j++)
if (pd(j,i)&&f[i-][j].tastyy){
for (int k=;k<=n;k++)
if (f[i][(j&(<<(k-)))].tastyy==-){
int cur=(j|(<<(k-)));//k-1
ll add=;
if (ad[f[i-][j].chos][k]) add=ad[f[i-][j].chos][k];
if (f[i-][j].tastyy+v[k]+add>=f[i][cur].tastyy){//放在括号内
f[i][cur].tastyy=f[i-][j].tastyy+v[k]+add;
f[i][cur].chos=k;
}
}
}
}
ll ans=;
for (int i=;i<=ma;i++)
if (f[m][i].tastyy>=){
if (f[m][i].tastyy>=ans) ans=f[m][i].tastyy;
}
printf("%I64d",ans);
return ;
}
说说正解。这道题当初电子科大那位讲过，我说怎么这么眼熟。用f[i][j]表示最后一个选 j 的状态 i 。第一层枚举所有状态，进入后判断是否选了m个更新答案，否则，第二层循环当前要选的点，如果当前状态没有选过，那么进入第三层，循环上一次能选的点，更新状态：f[(i|(1<<(j-1)))][j]=max(f[(i|(1<<(j-1)))][j],f[i][k]+ad[k][j]+v[j]) 。
AC代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define M 300000
#define maxn 20
#define ll long long
using namespace std;
int n,m,k;
ll v[maxn],f[M][maxn],ad[maxn][maxn],ans;
bool pd(int x)
{
int sum=;//sum=0
for (int i=;i<=n;i++)
if ((<<(i-))&x) sum++;//&x
if (sum==m) return true;
else return false;
}
int main()
{
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
cin>>n>>m>>k;
for (int i=;i<=n;i++)
scanf("%I64d",&v[i]);
for (int i=;i<=k;i++)
{
int x,y;
ll z;
scanf("%d%d%I64d",&x,&y,&z);
ad[x][y]=z;
}
for (int i=;i<n;i++)
f[(<<i)][i+]=v[i+];
int idx=;
for (int i=;i<=(<<n);i++)
{
if (pd(i)){
for (int j=;j<=n;j++)
if (f[i][j]>ans) ans=f[i][j];
}
else{
for (int j=;j<=n;j++)
{
if (((i>>(j-))&)==)
{//没有吃
for (int k=;k<=n;k++)
if ((i>>(k-))&)//枚举吃过的最后一个
{
if (f[i][k]+ad[k][j]+v[j]>f[(i|(<<(j-)))][j])
f[(i|(<<(j-)))][j]=f[i][k]+ad[k][j]+v[j];
}
}
}
}
}
printf("%I64d",ans);
return ;
}
第三题：
因为外来的入侵，国王决定在某些城市加派士兵。所有城市初始士兵数量为0。当城市i被加派了k名士兵时。城市?的所有子城市需要被加派k + 1名士兵。这些子城市的所有子城市需要被加派k +2名士兵。以此类推。当然，加派士兵的同时，国王也需要不断了解当前的情况。于是他随时可能询问以城市 i 为根的子树中的所有城市共被加派了多少士兵。你现在是国王的军事大臣，你能回答出国王的每个询问么？
输入格式
第一行，包含两个整数N,P代表城市数量以及国王的命令的数量。
第二行N −1个整数，表示2− N号每个节点的父亲节点。
接下来的P行，每行代表国王的一个命令，命令分两种:
A X K在城市X加入K个士兵
Q X 询问以城市X为根的子树中所有士兵数量的和。
n<=50000,p<=100000
解： 考试时用20多分钟打的暴力，过了50%。然后这套题就考了200。这是集训以来考的最好的一次，第4吧。
说正事。这道题的正解：dfs序+线段树。
dfs序：按照dfs的搜索顺序，一个节点的所有子树都是连续的标号，所以对于这个节点有一个最大区间，可以用线段树进行维护。（QAQ树套树-_-）
最终还是逃不过线段树。每一次操作u节点对于u的某一子树上的节点v而言，需要加上的值为k+dep[v]-dp[u]. dep[v]为节点本身的性质，而k-dep[u]为子树的性质。所以可以把它分为两部分处理。一个节点如果被操作了tot次，那么第一部分为tot*dep[v] , 对于子树而言，为tot*∑dep[v]。同样第二部分，每个子节点都是k-dep[u]，所以对于这棵子树为size*(k-dep[u]).
然后就是线段树的长长代码.....还要多练啊。提速。注意一些细节，毕竟代码长了容易犯小错误，而且这样的小错是很难找到的。我运气还算比较好。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 50005
#define ll long long
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)
#ifdef WIN32
#define AUTO "%I64d"
#else
#define AUTO "%lld"
#endif
using namespace std;
int n,q,ans,idx;
int tot,ne[maxn*],to[maxn*],he[maxn],id[maxn];
int xul[maxn],xur[maxn],depth[maxn]; void add(int a,int b)
{
tot++;to[tot]=b;ne[tot]=he[a];he[a]=tot;
}
void dfs_xu(int x,int fa,int dep)
{
depth[x]=dep;
xul[x]=++idx;//正序左
id[idx]=x;//反之
for (int i=he[x];i;i=ne[i])
if (to[i]!=fa){
dfs_xu(to[i],x,dep+);
}
xur[x]=idx;//右端点
}
/* /*-----------------xian_duan_shu-----------------------*/
struct pp{
ll dep,sum_tot,tot;//sum_tot: part_1
ll cha,sum_cha,size;//sum_cha作为子树的sum，cha 作为单点的cha,
};
pp tree[maxn*];
/*-------------add_dan----------------*/
void add_tot(int x,ll val)
{
tree[x].tot+=val;
tree[x].sum_tot+=val*tree[x].dep;
}
void add_cha(int x,ll val)
{
tree[x].cha+=val;
tree[x].sum_cha+=val*tree[x].size;
}
/*-------------------pushdown--------------------*/
void pushdown_tot(int cur)
{
if (!tree[cur].tot) return ;
add_tot(L(cur),tree[cur].tot);
add_tot(R(cur),tree[cur].tot);
tree[cur].tot=;
}
void pushdown_cha(int cur)
{
if(!tree[cur].cha) return ;
add_cha(L(cur),tree[cur].cha);
add_cha(R(cur),tree[cur].cha);
tree[cur].cha=;
}
/*----------------------uptate_sum---------------------*/
void uptate_tot(int cur)
{
tree[cur].sum_tot=tree[L(cur)].sum_tot+tree[R(cur)].sum_tot;
}
void uptate_cha(int cur)
{
tree[cur].sum_cha=tree[L(cur)].sum_cha+tree[R(cur)].sum_cha;
}
/*-----------------------------opreate-------------------------------*/
void change_tot(int cur,int l,int r,int x,int y,ll val)
{
if (l>=x&&r<=y)
{
add_tot(cur,val);
return ;
}
pushdown_tot(cur);
int mid=(l+r)>>;
if (x<=mid&&l<=y) change_tot(L(cur),l,mid,x,y,val);
if (y>=mid+&&x<=r) change_tot(R(cur),mid+,r,x,y,val);
uptate_tot(cur);
}
void change_cha(int cur,int l,int r,int x,int y,ll val)
{
if (l>=x&&r<=y)
{
add_cha(cur,val);
return ;
}
pushdown_cha(cur);
int mid=(l+r)>>;
if (x<=mid&&l<=y) change_cha(L(cur),l,mid,x,y,val);
if (y>=mid+&&x<=r) change_cha(R(cur),mid+,r,x,y,val);
uptate_cha(cur);
}
ll query(int cur,int l,int r,int x,int y)
{
if (x<=l&&r<=y)
return tree[cur].sum_tot+tree[cur].sum_cha;
pushdown_tot(cur);pushdown_cha(cur);
int mid=(l+r)>>;
ll an=;
if (x<=mid&&l<=y) an+=query(L(cur),l,mid,x,y);
if (y>=mid+&&x<=r) an+=query(R(cur),mid+,r,x,y);
return an;
}
/*----------------------build-----------------------*/ void update_build(int u)
{
tree[u].size=tree[L(u)].size+tree[R(u)].size;
tree[u].dep=tree[L(u)].dep+tree[R(u)].dep;//细节
}
void build(int l,int r,int u)
{
if (l==r)
{
tree[u].dep=depth[id[l]];
tree[u].size=;
return ;//****
}
int mid=(l+r)>>;
build(l,mid,L(u));
build(mid+,r,R(u));//mid+1
update_build(u);
}
/*-------------------------main----------------------------*/
int main()
{
freopen("c.in","r",stdin);
freopen("c.out","w",stdout);
cin>>n>>q;
for (int i=;i<=n;i++)
{
int x;
scanf("%d",&x);
add(x,i);
add(i,x);
}
dfs_xu(,,);
build(,n,);
while (q)
{
char c[];int x;
scanf("%s",c);
if (c[]=='A') {
int x;
ll y;
scanf("%d"AUTO,&x,&y);
change_tot(,,n,xul[x],xur[x],);
change_cha(,,n,xul[x],xur[x],y-depth[x]);
}
else {
int x;
scanf("%d",&x);
ll ans=query(,,n,xul[x],xur[x]);
printf(AUTO,ans);
printf("\n");
}
q--;
}
return ;
}