数数
solution
100分
每个数\(2^9\)枚举每一位属于哪一组,背包\(9^2DP\)判是否可行.每\(2\times10^6\)个打表,剩下的暴力判.
#include<cstdio>
#include<cstring>
#include<iostream>
#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<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#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<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#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<int> 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;
}