一开始不知道什么意思，看了hzwer的博客才知道：什么奇怪的题。

我都有些不好意思传代码了。

#include<cstdio>

int n,x,y=0;

int main(){
freopen("1603.in","r",stdin);
freopen("1603.out","w",stdout);
scanf("%d",&n);
n--;
while(n--){
    scanf("%d",&x);
    scanf("%d",&x);
    scanf("%d",&x);
    y^=x;
}
printf("%d\n",y);
return 0;
}

http://hzwer.com/?s=%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97

已经做了几题：

1

其实我早就会写多重背包了……只不过是写成做多次01背包而已……

看着大爷秒题，我心中感到自己好弱啊。

于是我就来理解一下多重背包的单调队列做法，并记录在这里。

对于一个物品有个数限制的背包，我们考虑状态转移方程：

f[now][j]=max(f[last][j],f[last][j-w[i]*k]+c[i]*k)，其中w[i]为重量，c[i]为价值。

感觉要枚举i,j,k，然后时间复杂度就爆炸了……

怎么办？用单调队列！

因为当我们取到了最大的f[last][j-w[i]*k]+c[i]*k时，再往下取k就没有意义了（不可能大于这个值）

所以我们维护一个单调队列，使队首为最大值，每次把不符合的队首删去，同时把队尾小于我们枚举的f[last][j-w[i]*k]+c[i]*k删去。

队列中存的是k，也就是记录当前取了多少个该物品，即可。

下面是一道例题。

----------------------------------------------------------------

超市购物

#include<cstdio>
#include<algorithm>
using namespace std;

int n,m,l[55],c[55],w[55],f[2][500005],q[500005];

int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
    scanf("%d %d %d",&c[i],&w[i],&l[i]);
}
for(int i=1;i<=n;i++){
    int now=i%2,last;
    last=now^1;
    for(int j=0;j<c[i];j++){
        int Rear=1,Front=1;
        q[1]=0;
        for(int k=0;k*c[i]+j<=m;k++){
            while(Front!=Rear && k-q[Front]>l[i])Front++;
            f[now][k*c[i]+j]=max(f[last][k*c[i]+j],f[last][q[Front]*c[i]+j]+w[i]*(k-q[Front]));
            while(Front<=Rear && f[last][q[Rear]*c[i]+j]+w[i]*(k-q[Rear])<=f[last][k*c[i]+j])Rear--;
            q[++Rear]=k;
        }
    }
}
printf("%d\n",f[n%2][m]);
return 0;
}

这是一个很裸的LCA。

觉得hzwer的LCA模版更加优美，于是膜拜了一下。

#include<cstdio>
#include<algorithm>
using namespace std;

int fa[1005][12],f[1005],n,q,en,h[1005],deep[1005],flg[1005];

struct Edge{
int b,v,next;
}e[2005];

void add(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}

void Yuchuli(int u){
flg[u]=1;
for(int i=1;i<=10;i++){
    if(deep[u]<(1<<i))break;
    fa[u][i]=fa[fa[u][i-1]][i-1];
}
for(int i=h[u];i;i=e[i].next){
    int v=e[i].b;
    if(flg[v])continue;
    f[v]=f[u]+e[i].v;
    fa[v][0]=u;
    deep[v]=deep[u]+1;
    Yuchuli(v);
}
}

int LCA(int u,int v){
if(deep[u]<deep[v])swap(u,v);
int dep=deep[u]-deep[v];
for(int i=0;i<=10;i++)if((1<<i)&dep)u=fa[u][i];
for(int i=10;i>=0;i--){
    if(fa[u][i]!=fa[v][i]){
        u=fa[u][i];
        v=fa[v][i];
    }
}
return u==v?u:fa[u][0];
}

int main(){
freopen("1602.in","r",stdin);
freopen("1602.out","w",stdout);
scanf("%d %d",&n,&q);
for(int i=1;i<n;i++){
    int sa,sb,sc;
    scanf("%d %d %d",&sa,&sb,&sc);
    add(sa,sb,sc);
    add(sb,sa,sc);
}
Yuchuli(1);
while(q--){
    int sa,sb;
    scanf("%d %d",&sa,&sb);
    printf("%d\n",f[sa]+f[sb]-2*f[LCA(sa,sb)]);
}
return 0;
}

这题是一个打表找规律。

据说这题可以dp，但是我并不想写。(懒癌晚期)

具体的找规律方式：点击这里

dp:点击这里

#include<cstdio>

int n,f[2505];

int main(){
freopen("1600.in","r",stdin);
freopen("1600.out","w",stdout);
scanf("%d",&n);
f[4]=1;
for(int i=5;i<=n;i++){
    if(i&1)f[i]=f[i-1]+(i-2)*(i/2-1);
    else f[i]=f[i-1]+i/2-1;
}
printf("%d\n",f[n]);
return 0;
}

这是一个筛法。

#include<cstdio>
#include<algorithm>
using namespace std;

int n,a[1000005],s[1000005],c[1000005],mx;

int main(){
freopen("1607.in","r",stdin);
freopen("1607.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    c[a[i]]++;
    mx=max(a[i],mx);
}
for(int i=1;i<=mx;i++){
    if(c[i]){
        for(int j=i;j<=mx;j+=i)s[j]+=c[i];
    }
}
for(int i=1;i<=n;i++)printf("%d\n",s[a[i]]-1);
return 0;
}

今天晚上ygp讲了一下单调队列，所以就写了这道题。

建立一个单调队列(升序)，然后维持该升序后利用二分查找符合标准的值作为ans。

据说线段树和单调栈也可以搞这题，那我也得到以后再写了(我现在不会线段树啊QAQ)

单调队列：

#include<cstdio>

int n,d,rear=1,lastans=0,counted=0;
char x;

struct Node{
int i,v;
}q[200005];

int main(){
freopen("1012.in","r",stdin);
freopen("1012.out","w",stdout);
scanf("%d %d",&n,&d);
while(n--){
    int w;
    scanf("%s %d",&x,&w);
    if(x=='Q'){
        int l=1,r=rear,mid,ans=-1;
        while(l<=r){
            mid=(l+r)/2;
            if(counted-q[mid].i+1>w){
                l=mid+1;
            }
            else {
                ans=mid;
                r=mid-1;
            }
        }
        printf("%d\n",q[ans].v);
        lastans=q[ans].v;
    }
    else {
        w=(w+lastans)%d;
        while(rear>0 && q[rear].v<w)rear--;
        q[++rear].i=++counted;
        q[rear].v=w;
    }
}
return 0;
}

今(昨)天晚上全在电脑前颓废掉了……现在才开始写作业。

然后发现作业好多……药丸了……

今天全在做水题（总比前几天一题不会好）

明晚有一场cf(UPD:其实是后天晚上)，但是估计又要滚粗……唉，还是打吧(立flag)

完。

01背包模版题。

#include<cstdio>
#include<algorithm>
using namespace std;

int n,v,a[5005],f[50005];

int main(){
freopen("1606.in","r",stdin);
freopen("1606.out","w",stdout);
scanf("%d %d",&v,&n);
for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++){
    for(int j=v;j>=a[i];j--){
        f[j]=max(f[j],f[j-a[i]]+a[i]);
    }
}
printf("%d\n",f[v]);
return 0;
}

计划做一做BZOJ上的USACO Silver……正好可以水一水刷题量了，提高代码能力

其实这是模仿jiry_2做的……

现在刷了多少题(以BZOJ搜索silver和资格赛关键词得到的题目作为基准)

8

我懒得写一句话题解了……为了文章量，每一道大水题我都会发一个题解。