抽象题目所求性质。
熟练模板。
T1:
题意：
把一序列重复，求一区间内某字符出现次数。
分析：
显然把超出该区间长度的直接乘法算就行了，注意一下并区间，区间从1开始导致len取不到的问题处理。思路很简单，但可能会被包装在比较难的题里面。
解锁新错误：读入优化没开longlong
不知道什么时候才能把这些傻逼错集齐。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<vector>
using namespace std;
#define ll long long
#define inf 1e8
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define minus(x) memset(x,-1,sizeof(x))
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "a"
const int Maxn=105;
ll len,lef,rig,ans,tot;
char a[Maxn];
long long read()
{
long long x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(long long)(ch-'0');ch=getchar();}
return x*f;
}
void init()
{
cin.getline(a+1,Maxn);
len=strlen(a+1);
for(int i=1;i<=len;i++)
if(a[i]=='B')
tot++;
lef=read();rig=read();
a[0]=a[len];
}
void work()
{
if(rig-lef+1LL>=len){
ans+=(rig-lef+1LL)/len*tot;
rig-=(rig-lef+1LL)/len*len;
}
if(rig>=lef){
for(int i=lef;i<=rig;i++)
if(a[i%len]=='B')ans+=1LL;
}
printf("%I64d",ans);
}
int main()
{
freopen(PROC".in","r",stdin);
freopen(PROC".out","w",stdout);
init();
work();
return 0;
}T2：
题意：
从n个蛋糕里选m个吃，且先吃i再吃j可能会使美味值增加，球最后能获得的最大美味值。
分析：
本来当成背包加一维来做，后来发现显然会重，于是刷刷刷敲了个状压，可惜还是没能挽救我的T3和静查。以及，估计时间复杂度的时候，这种状压的数值一定要精确，我差点以为要T。
状压表示选了哪些，然后枚举第二维（最后选的），再枚举前一个（要求在已选的里）来修改当前状态即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<vector>
using namespace std;
#define ll long long
#define inf 1e8
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define minus(x) memset(x,-1,sizeof(x))
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "b"
const int Maxn=20,Maxn2=3e5+5;
ll f[Maxn2][Maxn],c[Maxn][Maxn],ans;
ll n,m,k,x,y,a[Maxn];
ll read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
void init()
{
n=read();m=read();
k=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<=k;i++){
x=read();y=read();
c[x][y]=read();
}
}
void work()
{
for(int i=1;i<(1<<n);i++){
int flg=0;
ll ans2=0;
for(int j=1;j<=n;j++)
if(i&(1<<(j-1))){
for(int k=1;k<=n;k++)
if(i&(1<<(k-1))&&k!=j)
f[i][j]=max(f[i][j],f[i^(1<<(j-1))][k]+a[j]+c[k][j]);
if(!f[i][j])f[i][j]=a[j];
flg++;ans2=max(ans2,f[i][j]);
}
if(flg==m)ans=max(ans,ans2);
}
printf("%I64d",ans);
}
int main()
{
freopen(PROC".in","r",stdin);
freopen(PROC".out","w",stdout);
init();
work();
return 0;
}T3：
题意：
每次把一棵树及其子树上点加上一值（每往下走一层加1），在线询问某一点及其子树权值和。
分析：
记得一位大神说，如果你写的程序慢，说明你没发掘问题特有的性质。
这道题并不是一道简单的数据结构，里面涉及到本问题一个特有的特性：子节点比父节点多加1，这个可以很容易让我们想起来深度,然后就会发现，加上的权值里，是k-dep[fa]+dep[son]，然后本来采用线段树（因为一看就要带log)的难点：pushdown就可以迎刃而解：分别存k-dep[fa]的和以及dep[son]出现的次数即可；（这样就把每个点不同的值抽象成了同一种表示！）
然后线段树上维护这两个值即可。
吐槽一句：我线段树太丑了，标记还没累加直接T成暴力，幸好NOIP前发现了不然要完。
再吐槽一句：听说我压码能力很强，把别人200+行的代码带模板直接压成了140？（手动萌币
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<vector>
#define ll long long
#define inf 1e8
#define clr(x) memset(x,0,sizeof(x))
#define maxen(x) memset(x,127,sizeof(x))
#define maxer(x) memset(x,31,sizeof(x))
#define minus(x) memset(x,-1,sizeof(x))
#define minn(a,b,c) min(a,min(b,c))
#define maxx(a,b,c) max(a,max(b,c))
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define PROC "c"
const int Maxn=5e4+5;
int fr[Maxn],tov[Maxn],w[Maxn],wrev[Maxn],tail[Maxn];
int dep[Maxn];
int n,p,cnt;
struct node
{
int lef,rig,bj2;
ll bj,tot,sum,depsum,a;
}a[Maxn*4];
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
void addedge(int cur)
{
int nowy=read();
tov[cur]=fr[nowy];
fr[nowy]=cur;
}
void dfs(int cur,int fa)
{
dep[cur]=dep[fa]+1;
w[cur]=++cnt;wrev[cnt]=cur;
for(int i=fr[cur];i;i=tov[i])
dfs(i,cur);
tail[cur]=cnt;
}
void build(int u,int lef,int rig)
{
a[u].lef=lef;a[u].rig=rig;
if(lef==rig){
a[u].depsum=dep[wrev[lef]];
return;
}
int mid=(a[u].lef+a[u].rig)>>1;
build(2*u,lef,mid);
build(2*u+1,mid+1,rig);
a[u].depsum=a[2*u].depsum+a[2*u+1].depsum;
}
void init()
{
n=read();p=read();
for(int i=2;i<=n;i++)
addedge(i);
dfs(1,0);
build(1,1,n);
}
void pushdown(int u)
{
a[u].tot+=a[u].bj2;
a[u].a+=a[u].bj*(a[u].rig-a[u].lef+1);
a[u].sum+=a[u].bj2*a[u].depsum+a[u].bj*(a[u].rig-a[u].lef+1);
if(a[u].lef!=a[u].rig){
a[2*u].bj+=a[u].bj;
a[2*u+1].bj+=a[u].bj;
a[2*u].bj2+=a[u].bj2;
a[2*u+1].bj2+=a[u].bj2;
}
a[u].bj=a[u].bj2=0;
}
void update(int u,int lef,int rig,int wor)
{
if(a[u].lef==lef&&a[u].rig==rig){
a[u].bj+=wor;
a[u].bj2++;
pushdown(u);
return;
}
if(a[u].bj2)pushdown(u);
int mid=(a[u].lef+a[u].rig)>>1;
if(rig<=mid)update(2*u,lef,rig,wor);
else if(lef>mid)update(2*u+1,lef,rig,wor);
else {
update(2*u,lef,mid,wor);
update(2*u+1,mid+1,rig,wor);
}
if(a[2*u].bj2)pushdown(2*u);
if(a[2*u+1].bj2)pushdown(2*u+1);
a[u].sum=a[2*u].sum+a[2*u+1].sum;
}
ll query(int u,int lef,int rig)
{
if(a[u].bj2)pushdown(u);
if(a[u].lef==lef&&a[u].rig==rig)
return a[u].sum;
int mid=(a[u].lef+a[u].rig)>>1;
if(rig<=mid)return query(2*u,lef,rig);
else if(lef>mid)return query(2*u+1,lef,rig);
else return query(2*u,lef,mid)+query(2*u+1,mid+1,rig);
}
void work()
{
for(int i=1;i<=p;i++){
char b[5];
scanf("%s",b);
if(b[0]=='Q'){
int u=read();
printf("%I64d\n",query(1,w[u],tail[u]));
}
else {
int u=read();
update(1,w[u],tail[u],read()-dep[u]);
}
}
}
int main()
{
freopen(PROC".in","r",stdin);
freopen(PROC".out","w",stdout);
init();
work();
return 0;
}