11月10日——离noip还有9天【你的名字……】与[一个神奇的函数]

时间已经变成一位数了，今天的考试还是BB，
会做的一定AC，不会的就暴力了。
所以今天状压dp忘了滚动数组！！！（有什么关系吗？）
因多人反映(其实就只有两个人在那儿瞎bb)，本人决定不止发“车万”的图！！！！

为你的名字打广告。

你的名字，百度云盘：
http://pan.baidu.com/s/1bpqqdxP
http://pan.baidu.com/s/1jILPSO2

A

（最近看了“你叫啥子”（雾）“你的名字”，新城海终于不开刀片厂了……推荐大家看看）

Statement
给出一个长度不超过100只包含’B’和’R’的字符串，将其无限重复下去。
比如，BBRB则会形成
BBRBBBRBBBRB
现在给出一个区间[l,r]询问该区间内有多少个字符’B’(区间下标从1开始)

Input
第一行为一个只包含’B’和’R’的字符串
第二行为两个整数，表示l和r

Output
输出[l,r]区间内字符’B’的数量

Sample Input
BBRB
4 8

Sample Output
4

Limit
1<=|S|<=100(字符串长度大于等于1，小于等于100)
1<=i<=r<=1e18

太水了（太甜了），模拟？暴力？不如A题。

题解。。。。

直接取模，然后模拟取模的部分
对于每一段直接乘以’B’的数量，简单粗暴。

两份代码

#include<bits/stdc++.h>//这玩意考试时不能用
using namespace std;

char s[200];
typedef long long LL;
LL res,len;
LL cal(LL i)
{
    LL ans=i/len*res;
    LL rem=i%len;
for(int i=0;i<rem;++i)
if(s[i]=='B')++ans;
return ans;
}
int main()
{
int T;
//scanf("%d",&T);
//for(int cas=1;cas<=T;++cas)
//{
scanf("%s",s);
        res=0;
        len=strlen(s);
for(int i=0;s[i]!='\0';++i)
if(s[i]=='B')++res;
        LL i,j;
scanf("%I64d%I64d",&i,&j);
//printf("Case #%d: %I64d\n",cas,cal(j)-cal(i-1));
printf("%I64d\n",cal(j)-cal(i-1));
///}
return 0;
}

//注释了很多不明所以的标答。。。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#define ll long long
using namespace std;
ll l,r,len,add,L,R,ans,head,tail,K;
char s[105];
int main(){
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
scanf("%s",s+1);
    len=strlen(s+1);
scanf("%I64d%I64d",&l,&r);  
for (int i=1;i<=len;i++)
if(s[i]=='B') add++;
if(l%len==0) head=l;
else head=(l/len+1)*len;
    tail=(r/len)*len;
    K=(tail-head)/len;
    ans=ans+K*add;
int sta;
if(l%len==0) sta=len;
else sta=l%len;
for (int i=1;i<=head-l+1;i++){
if(s[sta]=='B') ans++;
        sta++;
    }
for (int i=1;tail+i<=r;i++)
if(s[i]=='B') ans++;
cout<<ans;
return 0;
} 

本弱蒟的code。

B

【题目描述】
我们要从n种食物选m个出来，安排一个顺序吃掉它（们），每种食物有个美味值ai，然后我们有k个规则，每个规则有 xi, yi 和 ci三个数，如果吃完第xi种食物接下来马上吃第yi种食物，第j种食物的美味值会增加ci。每种食物至多吃一个，求美味值最大的和是多少？

【输入格式】
第一行有三个数n,m,k,k代表有k个规则(0<=k<=n*(n-1))。
第二行有n个数字代表每个食物的美味值。
接下去有k行，每行三个数xi,yi,ci。保证没有任意两个规则的xi和yi同时相同。

【输出格式】
一行一个数代表答案

【sample input1】
2 2 1
1 1
2 1 1
【sample output1】
3

【sample input 2】
4 3 2
1 2 3 4
2 1 5
3 4 2
【sample output 2】
12

【数据范围】
30% m<=n<=5 ,0<=ci,ai<=1e5
100% m<=n<=18，0<=ci,ai<=1e9

思路

其实一开始就知道是dp，但各种dp都gg，状压dp忘了可以用滚动数组就没写，错的太gg了！！！！
其实数据那么小，可以直接状压。
dp[i][j]表示状态为i，最后一个吃的是第j种食物的最大的和。
dp[13][2]=dp[(0001101)][2]
表示已经吃了第0种，第2种，第3种食物，最后吃的是第2种。
for(int i=1;i<(1< < n);i++)//枚举所有可能的状态，记得预处理dp[1 < < i][i]=ai
如果已经有m个了：for(int j=0;j< n;j++)ans=max(ans,dp[i][j]);
否则：
for(int k=0;k< n;k++)//枚举哪一个没吃
if(((i>>k)&1)==0)//如果这一位为0表示没吃
for(int j=0;j< n;j++)//枚举哪一个是最后吃的
if((1<< j)&i)//如果这一位为1表示吃了
dp[i|(1<< k)][k]=max(dp[i][j]+mp[j][k]+a[k],dp[i|(1<< k)][k]);

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long int lli;

lli Bitmask [18][(1<<18)];
lli value_food[18];
lli relation[18][18];

int main()
{
    freopen("b.in", "r", stdin);
    freopen("b.out", "w", stdout);
    lli n,m,k;cin>>n>>m>>k;
for(lli i=0;i<n;i++)cin>>value_food[i];
while(k--)
    {
        lli x,y,z;cin>>x>>y>>z; x--,y--;
        relation[x][y]=z;
    }

    lli javab = -111111111111111111111LL;//INFINITY;
for(lli i =0;i<(1<<n);i++)
    {
if(__builtin_popcount(i)>m)continue;
for(lli j=0;j<n;j++)
        {
if( ((1<<j) & i) == 0 )continue;
else if( __builtin_popcount(i)==1 )Bitmask[j][i] = value_food[j];
else
            {
                lli Max = -111111111111111111111LL;//INFINITY;
for(lli f=0;f<n;f++)
                {
if( (((1<<f) & i ) != 0) && (f!=j) )
                    {
                        Max = max( Max , Bitmask[f][(i & ~(1<<j))] + relation[f][j] + value_food[j] );
                    }
                }
                Bitmask[j][i] = Max;
            }

if(__builtin_popcount(i)==m) javab = max (javab,Bitmask[j][i]);
        }
    }

//for(lli i=0;i<n;i++) if(( (1<<i) & javab) != 0 )cout<<i+1<<" ";
cout<<javab<<"\n";
return 0;
}

……小编内心决定以后多用状压dp，因为……
》》》》__builtin_popcount(i)这函数太bug了吧！！
详见另一份博客
然后我就迎来了今天最大的挑（pian）战（fen）。

C

（这出题人也是够了，nm图片格式，**画质……）
我真的没有办法了，直接上图吧

题解

C
对树做一次dfs生成一个2*N的序列,L[u],R[u]分别表示刚进入子树u时的dfs序列位置和刚处理完子树u时的dfs序列位置。则l[u]到r[u]这一段便是子树u的所有节点。
我们对每个节点记录两个值cnt，k，
每个节点v的实际值w = cnt *dep[v] + k,则原操作add u x可以看成是对每个子树中的cnt值+1，k值+ x - dep[u]，这样便可以用线段树对DFS序列进行区间操作了。
……看起来就不简单，
考试时先打上了线段树后就不知如何了，最后暴力得了50分。。。。

标答

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;
const int MaxN = 50005;
const int MaxE = MaxN * 2;
const int MaxS = MaxN * 4;

struct Edge
{
int to;
    Edge* next;
} memo[MaxE], *cur, *g[MaxN];
int dep[MaxN], l[MaxN], r[MaxN], N, K;
int ax[MaxN];

void init()
{
for (int i = 1; i <= N; i++)
        g[i] = NULL;
    cur = memo;
    K = 0;
}

void add_edge(int u, int v)
{
    cur->to = v;
    cur->next = g[u];
    g[u] = cur++;
}

void DFS(int u, int f)
{
int v;
    l[u] = ++K;
    ax[K] = u;
    dep[u] = dep[f] + 1;
for (Edge* it = g[u]; it; it = it->next)
    {
        v = it->to;
if (v != f)
            DFS(v, u);
    }
    r[u] = K;
}

struct Seg
{
int l, r;
    ll sumK, delK;
    ll base, sumD, delCnt;
} seg[MaxS];

void insK(int k, ll v)
{
    seg[k].sumK += v * (seg[k].r - seg[k].l + 1);
    seg[k].delK += v;
}

void insCnt(int k, ll v)
{
    seg[k].delCnt += v;
    seg[k].sumD += seg[k].base * v;
}

void update(int k)
{
    seg[k].sumD = seg[k << 1].sumD + seg[k << 1 | 1].sumD;
    seg[k].sumK = seg[k << 1].sumK + seg[k << 1 | 1].sumK;
}

void pushdown(int k)
{
if (seg[k].delK)
    {
        insK(k << 1, seg[k].delK);
        insK(k << 1 | 1, seg[k].delK);
        seg[k].delK = 0;
    }
if (seg[k].delCnt)
    {
        insCnt(k << 1, seg[k].delCnt);
        insCnt(k << 1 | 1, seg[k].delCnt);
        seg[k].delCnt = 0;
    }
}

void init(int k, int l, int r)
{
    seg[k].l = l;
    seg[k].r = r;
    seg[k].sumK = seg[k].delK = 0;
    seg[k].sumD = seg[k].delCnt = 0;
if (l == r)
    {
        seg[k].base = dep[ax[l]];
return;
    }
int mid = (l + r) >> 1;
    init(k << 1, l, mid);
    init(k << 1 | 1, mid + 1, r);
    seg[k].base = seg[k << 1].base + seg[k << 1 | 1].base;
}

void addK(int k, int l, int r, ll v)
{
if (seg[k].l > r || seg[k].r < l)
return;
if (seg[k].l >= l && seg[k].r <= r)
    {
        insK(k, v);
return;
    }
    pushdown(k);
    addK(k << 1, l, r, v);
    addK(k << 1 | 1, l, r, v);
    update(k);
}

void addCnt(int k, int l, int r, ll v)
{
if (seg[k].l > r || seg[k].r < l)
return;
if (seg[k].l >= l && seg[k].r <= r)
    {
        insCnt(k, v);
return;
    }
    pushdown(k);
    addCnt(k << 1, l, r, v);
    addCnt(k << 1 | 1, l, r, v);
    update(k);
}

ll read(int k, int l, int r)
{
if (seg[k].l > r || seg[k].r < l)
return 0;
if (seg[k].l >= l && seg[k].r <= r)
    {
return seg[k].sumK + seg[k].sumD;
    }
    pushdown(k);
return read(k << 1, l, r) + read(k << 1 | 1, l, r);
}

int main()
{
int T, x;
int Q, u, cas = 1;
char op[5];

    freopen("soldier.in", "r", stdin);
    freopen("soldier.out", "w", stdout);

scanf("%d%d", &N, &Q);
    init();
for (int i = 2; i <= N; i++)
    {
scanf("%d", &x);
        add_edge(x, i);
        add_edge(i, x);
    }
    dep[0] = -1;
    DFS(1, 0);
    init(1, 1, N);
while (Q--)
    {
scanf("%s", op);
if (op[0] == 'Q')
        {
scanf("%d", &u);
printf("%I64d\n", read(1, l[u], r[u]));
        }
else
        {
scanf("%d%d", &u, &x);
            addK(1, l[u], r[u], x - dep[u]);
            addCnt(1, l[u], r[u], 1);
        }
    }

return 0;
}

今天就到这里吧！！