数数

solution

100分

每个数\(2^9\)枚举每一位属于哪一组,背包\(9^2DP\)判是否可行.每\(2\times10^6\)个打表,剩下的暴力判.

#include
#include
#include
#define N 15
#define M 41
#define K 2000000
using namespace std;
int a[N],f[M],l,r;
int g[1000]={0,832547,1744956,2647716,3526440,4366880,5304766,6290672,7272530,8238396,9182258,10130918,11103529,12080513,13045216,13996047,14945703,15913605,16892727,17858307,18810719,19753895,20731414,21684697,22655525,23601310,24542752,25521340,26480512,27450344,28401296,29330880,30294677,31267680,32207445,33151141,34066147,35032633,36000291,36928875,37865237,38762309,39721014,40673581,41617398,42514127,43401357,44345895,45290065,46226307,47111407,48049293,49035199,50017057,50982923,51926786,52900916,53897101,54894264,55882154,56858336,57847816,58846682,59846494,60842736,61832643,62825256,63822618,64821477,65818159,66811192,67801399,68800631,69792675,70790949,71781713,72770527,73769968,74763402,75759527,76751555,77734047,78730989,79728413,80714563,81704149,82675413,83671395,84668372,85646750,86626601,87586711,88579192,89572024,90554096,91513942,92473876,93464335,94454295,95441662,96400455,97349115,98321726,99298710,100263413,101214244,102203724,103202590,104202402,105198644,106188552,107167293,108153408,109140447,110124934,111104170,112096906,113093027,114091415,115087418,116080738,117067923,118057868,119048442,120037757,121025141,122014753,123010235,124005151,124999107,125991518,126975151,127964407,128955576,129941988,130927549,131904861,132896096,133888198,134870790,135853348,136826261,137814171,138803944,139789107,140761869,141729694,142714340,143704363,144687319,145654892,146604548,147572450,148551572,149517152,150469564,151462177,152459539,153458398,154455080,155448113,156440849,157436970,158435358,159431361,160424682,161397209,162373648,163366196,164342307,165316242,166305808,167302421,168296439,169291181,170282583,171271000,172265321,173259685,174255102,175244787,176221893,177200499,178195519,179174053,180151503,181136659,182130169,183125306,184112942,185104838,186083111,187073418,188063818,189056830,190034891,191002063,191979011,192969700,193946033,194913068,195856244,196833763,197787046,198757874,199703659,200693866,201693098,202685142,203683416,204674180,205661365,206651310,207641884,208631199,209618583,210608149,211604762,212598780,213593522,214584925,215547464,216534065,217499718,218484410,219446727,220429515,221427505,222413231,223409872,224393574,225378825,226368592,227358537,228346119,229333643,230317495,231311785,232303172,233291625,234281777,235250988,236239191,237209396,238197024,239165608,240132946,241123530,242099344,243089392,244056062,244997504,245976092,246935264,247905096,248856048,249844862,250844303,251837737,252833862,253825890,254815502,255810984,256805900,257799856,258792267,259780684,260775005,261769369,262764786,263754471,264737259,265735249,266720975,267717616,268701319,269671136,270662426,271637394,272626656,273606213,274591389,275587811,276582159,277572087,278564272,279545055,280538004,281529559,282513143,283502662,284478850,285470820,286457275,287450750,288427696,289394488,290384616,291361419,292349648,293317366,294246950,295210747,296183750,297123515,298067211,299049703,300046645,301044069,302030219,303019805,304003438,304992694,305983863,306970275,307955836,308932942,309911548,310906568,311885102,312862552,313847803,314837570,315827515,316815097,317802621,318787797,319784219,320778567,321768495,322760681,323713304,324683475,325665009,326618472,327585453,328558745,329553519,330549495,331524705,332510934,333479831,334465932,335454856,336433663,337405293,338369679,339346589,340337374,341311777,342276694,343191700,344158186,345125844,346054428,346990790,347962054,348958036,349955013,350933391,351913242,352890554,353881789,354873891,355856483,356839041,357824197,358817707,359812844,360800480,361792376,362776228,363770518,364761905,365750358,366740510,367721293,368714242,369705797,370689381,371678900,372652192,373646966,374642942,375618152,376604382,377538051,378513505,379489566,380427196,381388631,382345623,383337697,384329876,385303519,386266143,387225366,388207745,389195237,390169258,391130374,392027446,392986151,393938718,394882535,395779264,396739374,397731855,398724687,399706759,400666605,401639518,402627428,403617201,404602364,405575126,406553399,407543706,408534106,409527118,410505179,411474390,412462593,413432798,414420426,415389010,416365198,417357168,418343623,419337098,420314044,421282941,422269042,423257966,424236773,425208403,426165395,427157469,428149648,429123291,430085916,430994511,431957867,432917585,433871463,434779290,435727270,436714737,437700549,438680925,439626259,440513489,441458027,442402197,443338439,444223539,445183473,446173932,447163892,448151259,449110052,450077877,451062523,452052546,453035502,454003075,454970247,455947195,456937884,457914217,458881252,459848590,460839174,461814988,462805036,463771706,464738498,465728626,466705429,467693658,468661376,469625762,470602672,471593457,472567860,473532777,474492000,475474379,476461871,477435892,478397008,479344988,480332455,481318267,482298643,483243978,484139891,485087032,486035608,486981265};
inline bool chk(int k){
    register int tot=0,cnt=0;
    while(k){
        cnt+=(a[++tot]=k%10);k/=10;
    }
    if(cnt&1) return false;
    memset(f,0,sizeof(f));
    f[0]=true;
    for(register int i=1;i<=tot;++i){
        for(register int j=cnt>>1;j>=a[i];--j)
            f[j]|=f[j-a[i]];
        if(f[cnt>>1]) return true;
    }
    return f[cnt>>1];
}
inline int ask(int k){
    if(!k) return 0;
    register int ret=g[k/K];
    for(register int i=k/K*K+1;i<=k;++i)
        if(chk(i)) ++ret;
    return ret;
}
inline void Aireen(){
    scanf("%d%d",&l,&r);
    printf("%d\n",ask(r)-ask(l-1));
}
int main(){
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}
/*
    printf("g[1000]={0");
    for(ri i=1;i<1000000000;++i){
        if(chk(i)) ++sum;
        if(!(i%2000000)) printf(",%d",sum);
    }
    printf("};");
*/

红与蓝

solution

100分

\(f[i]\)表示以\(i\)为根的子树的下一层孩子红色\(-\)蓝色的个数.
\(f[i]>0\),红胜;\(f[i]=0\),先手胜;\(f[i]<0\),蓝胜.
如果根节点是红胜,第一轮可以选择的叶子为所有未着色的叶子.
如果根节点是先手胜,第一轮可以选择的叶子为沿着先手胜或蓝只比红多\(1\)的子树走下去的叶子.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 100005
using namespace std;
struct graph{
    int nxt,to;
}e[N];
int a[N],f[N],g[N],ans[N],n,t,cnt;
inline int read(){
    int ret=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        ret=(ret<<1)+(ret<<3)+c-'0';
        c=getchar();
    }
    return ret*f;
}
inline void addedge(int x,int y){
    e[++cnt]=(graph){g[x],y};g[x]=cnt;
}
inline void dfs(int u){
    f[u]=a[u];
    for(int i=g[u];i;i=e[i].nxt){
        dfs(e[i].to);f[u]+=(f[e[i].to]>0)-(f[e[i].to]<0);
    }
}
inline void dfs2(int u){
    if(!f[u]&&!g[u]) ans[++cnt]=u;
    for(int i=g[u];i;i=e[i].nxt)
        if(!f[e[i].to]||f[e[i].to]==-1) dfs2(e[i].to);
}
inline void Aireen(){
    t=read(); 
    while(t--){
        n=read();cnt=0;
        memset(f,0,sizeof(f));
        memset(g,0,sizeof(g));
        for(int i=1;i<=n;++i)
            addedge(read(),i);
        for(int i=1;i<=n;++i){
            a[i]=read();
            if(!a[i]) a[i]=1;
            else if(a[i]>0) a[i]=-1;
            else a[i]=0;
        }
        dfs(1);cnt=0;
        if(f[1]>0){
            for(int i=1;i<=n;++i)
                if(!g[i]&&!f[i]) ans[++cnt]=i;
        }
        else if(!f[1]){
            dfs2(1);
            sort(ans+1,ans+1+cnt);
        }
        else cnt=-1;
        printf("%d",cnt);
        for(int i=1;i<=cnt;++i)
            printf(" %d",ans[i]);
        printf("\n");
    }
}
int main(){
    freopen("rab.in","r",stdin);
    freopen("rab.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}

炮塔

solution

100分

两个炮塔的相交路径可以看为一条射线只拐一次得到的.
设竖直方向射线方向不变,水平方向射线方向调转\(\pi\),这样两个炮塔的相交路径可以转化成一条拐了一次的射线.
考虑最小割,求使此路径不存在的最小代价.
设边\((u,v)\)表示选取\(u\),相邻的点按方向连接建边.
求出每个方向上敌人的最大值\(max\),则\((u,v)\)边权为\(max-p_u\).
为了保证只拐一次,将点\((x,y)\)按行列\(i,j\)拆点,\((i_{(x,y)},j_{(x,y)})=+\infty\).
\(s\)向攻击竖直方向的炮塔连一条\(+\infty\)的有向边,攻击水平方向的炮塔向\(t\)连一条\(+\infty\)的有向边.
\(ans=\sum{p_i}-Mincut\).

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 55
#define K 5005
#define M 250005
#define INF 2497500
using namespace std;
struct graph{
    int nxt,to,f;
}e[M];
int a[N][N],x[N][N],y[N][N],g[K],dep[K],n,m,s,t,cnt,ans;
queue q;
inline void addedge(int x,int y,int f){
    e[++cnt]=(graph){g[x],y,f};g[x]=cnt;
}
inline void adde(int x,int y,int f){
    addedge(x,y,f);addedge(y,x,0);
}
inline bool bfs(int u){
    memset(dep,0,sizeof(dep));
    q.push(u);dep[s]=1;
    while(!q.empty()){
        u=q.front();q.pop();
        for(int i=g[u];i;i=e[i].nxt)
            if(e[i].f>0&&!dep[e[i].to]){
                q.push(e[i].to);
                dep[e[i].to]=dep[u]+1;
            }
    }
    return dep[t];
}
inline int dfs(int u,int f){
    if(u==t) return f;
    int ret=0;
    for(int i=g[u],d;i&&f;i=e[i].nxt)
        if(e[i].f>0&&dep[e[i].to]>dep[u]){
            d=dfs(e[i].to,min(e[i].f,f));
            e[i].f-=d;e[i^1].f+=d;f-=d;ret+=d;
        }
    if(!ret) dep[u]=-1;
    return ret;
}
inline int dinic(){
    int ret=0;
    while(bfs(s))
        ret+=dfs(s,INF);
    return ret;
}
inline void Aireen(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            scanf("%d",&a[i][j]);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            x[i][j]=++cnt;y[i][j]=++cnt;
        }
    s=cnt+1;t=s+1;cnt=1;
    for(int i=1,mx;i<=n;++i)
        for(int j=1;j<=m;++j){
            if(a[i][j]==-1){
                adde(s,x[i][j],INF);
                mx=0;
                for(int k=i-1;k>0;--k){
                    mx=max(mx,a[k][j]);
                }
                a[i][j]=0;
                for(int k=i;k>0;--k)
                    adde(x[k][j],x[k-1][j],mx-a[k][j]);
                ans+=mx;
            }
            else if(a[i][j]==-2){
                adde(s,x[i][j],INF);
                mx=0;
                for(int k=i+1;k<=n;++k)
                    mx=max(mx,a[k][j]);
                a[i][j]=0;
                for(int k=i;k<=n;++k)
                    adde(x[k][j],x[k+1][j],mx-a[k][j]);
                ans+=mx;
            }
            else if(a[i][j]==-3){
                adde(y[i][j],t,INF);
                mx=0;
                for(int k=j-1;k>0;--k)
                    mx=max(mx,a[i][k]);
                a[i][j]=0;
                for(int k=j;k>0;--k)
                    adde(y[i][k-1],y[i][k],mx-a[i][k]);
                ans+=mx;
            }
            else if(a[i][j]==-4){
                adde(y[i][j],t,INF);
                mx=0;
                for(int k=j+1;k<=m;++k)
                    mx=max(mx,a[i][k]);
                a[i][j]=0;
                for(int k=j;k<=m;++k)
                    adde(y[i][k+1],y[i][k],mx-a[i][k]);
                ans+=mx;
            }
            else adde(x[i][j],y[i][j],INF);
        }
    printf("%d\n",ans-dinic());
}
int main(){
    freopen("tower.in","r",stdin);
    freopen("tower.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}