A Coder (HDU
4288，与Codeforces
85D相同)
应该用线段树写，我是块状链表水过了
#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=320*320;
struct Query
{
char s[5];
int x;
}q[N];
int a[N],sz[N],n;
ll sum[320][5];
int main()
{
while(scanf("%d",&n)!=EOF)
{
int k=0,block=0;
while(block*block<n) block++;
for(int i=0;i<n;i++)
{
scanf("%s",q[i].s);
if(q[i].s[0]!='s') scanf("%d",&q[i].x),a[k++]=q[i].x;
}
sort(a,a+k);
k=unique(a,a+k)-a;
map<int,int>p;
for(int i=0;i<k;i++) p[a[i]]=i;
memset(a,0,sizeof(a));
memset(sz,0,sizeof(sz));
memset(sum,0,sizeof(sum));
for(int i=0;i<n;i++)
{
if(q[i].s[0]!='s')
{
int pos=p[q[i].x],rt=pos/block;
int l=rt*block,r=l+block,k=0;
a[pos]=q[i].s[0]=='a'?q[i].x:0;
memset(sum[rt],0,sizeof(sum[rt]));
for(int i=l;i<r;i++) if(a[i]) sum[rt][k++%5]+=a[i];
sz[rt]=k;
}
else
{
ll ans=0;k=2;
for(int i=0;i<block;i++) ans+=sum[i][k],k=(k-sz[i]+50000)%5;
printf("%I64d\n",ans);
}
}
}
return 0;
}
B Control (HDU
4289)
网络流求最小割，将每个点拆成两个，流量为点权值
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=444,M=88888;
FlowNetwork sap;
int main()
{
int n,m,s,d,u,v;
while(scanf("%d%d%d%d",&n,&m,&s,&d)!=EOF)
{
sap.init();
for(int i=1; i<=n; i++) scanf("%d",&v),sap.add(i,i+n,v);
while(m--)
{
scanf("%d%d",&u,&v);
sap.add(u+n,v,inf);
sap.add(v+n,u,inf);
}
printf("%d\n",sap.sap(s,n+d,n*2));
}
return 0;
}
C
Counting Formations (HDU
4290)
D
A Short problem (HDU
4291)
先求出g(g(g(n)))每一层的循环节
#include<iostream>
using namespace std;
int main()
{
long long mod=1000000007,a,b,c,cnt;
for(int i=0;i<3;i++)
{
a=0,b=1,cnt=0;
while(1)
{
c=(3*b+a)%mod;
a=b,b=c;cnt++;
if(a==0&&b==1) break;
}
cout<<cnt<<endl;
mod=cnt;
}
return 0;
}
记循环节为a=222222224,b=183120,c=240.
则g(g(g(n)))%mod=g(g(g(n%c)%b)%a)%mod,再利用矩阵二分算一下即可：
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
struct Mat
{
int a[2][2];
Mat(){memset(a,0,sizeof(a));}
Mat mul(Mat &b,int mod)
{
Mat c;
for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++)
c.a[i][j]=(c.a[i][j]+(ll)a[i][k]*b.a[k][j])%mod;
return *this=c;
}
Mat cal(int n,int mod)
{
Mat b=*this,c;
c.a[0][0]=c.a[1][1]=1;
while(n)
{
if(n&1) c.mul(b,mod);
n>>=1;
b.mul(b,mod);
}
return *this=c;
}
};
int g(int n,int mod)
{
if(n==0) return 0;
Mat a;
a.a[0][0]=3;a.a[1][1]=0;
a.a[0][1]=a.a[1][0]=1;
a.cal(n-1,mod);
return a.a[0][0];
}
int main()
{
ll n;
while(cin>>n) cout<<g(g(g(n%240,183120),222222224),1000000007)<<endl;
return 0;
}
E
Food (HDU
4292)
网络流，建s,e，将人拆点，从s到food连边，food到人连边，人到人‘连边，人’到drink连边，drink到e连边，求出最大流即可
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=888,M=222222;
FlowNetwork sap;
char str[N];
int main()
{
int n,f,d;
while(scanf("%d%d%d",&n,&f,&d)!=EOF)
{
sap.init();
int s=0,e=n*2+f+d+1,x;
for(int i=1;i<=f;i++) scanf("%d",&x),sap.add(s,i,x);
for(int i=n*2+f+1;i<e;i++) scanf("%d",&x),sap.add(i,e,x);
for(int i=f+1;i<=f+n;i++) sap.add(i,i+n,1);
for(int i=1;i<=n;i++)
{
scanf("%s",str);
for(int j=0;str[j];j++) if(str[j]=='Y') sap.add(j+1,i+f,inf);
}
for(int i=1;i<=n;i++)
{
scanf("%s",str);
for(int j=0;str[j];j++) if(str[j]=='Y') sap.add(n+f+i,n*2+f+j+1,inf);
}
printf("%d\n",sap.sap(s,e,e-s+1));
}
return 0;
}
F
Groups (HDU
4293)
相同的区间算一个，区间权值++，但不能超过区间长度。然后就是N个区间，从中选择若干个区间使得权值之和尽可能大。
dp[i]表示选择最后一个区间以i为右端点时能获得的最大权值。
#include<map>
#include<cstdio>
#include<cstring>
using namespace std;
typedef pair<int,int>tp;
int dp[555];
int main()
{
int n,a,b;
while(scanf("%d",&n)!=EOF)
{
memset(dp,0,sizeof(dp));
map<tp,int>mp;
for(int i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
if(a+b+1<=n&&mp[tp(a+1,n-b)]<n-b-a) mp[tp(a+1,n-b)]++;
}
for(map<tp,int>::iterator it=mp.begin();it!=mp.end();it++)
for(int i=0;i<it->first.first;i++)
dp[it->first.second]=max(dp[it->first.second],dp[i]+it->second);
int ans=0;
for(int i=0;i<=n;i++) ans=max(ans,dp[i]);
printf("%d\n",ans);
}
return 0;
}
G
Multiple (HDU
4294)
①由一个数组成，由抽屉原理可知长度一定不超过n，否则会存在长度为a时与长度为b时对n取模结果相同，即循环节为b-a+1,且循环中存在某个数%n==0
②由两个数组成，一定可以。对任意n，则长度1-n且全为1的数中一定存在两个长度i,j的数对n取模相同，现在用较大的数减去较小的数，则结果为111111000000，由两个数组成。
对于每次计算，只需要用pre[k]指向第一次k=x%n对应的x。现在只要保证第一次搜到k时对应的x最小，那么每次从pre[0]一直找到pre[w]=-1，对应就是答案。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=10010;
int q[N],pre[N],val[N];
bool vis[N];
char s[N],ss[N];
void bfs(int x,int y,int n,int k)
{
memset(vis,0,sizeof(vis));
int low=0,up=-1;
if(x) q[++up]=x%n,pre[x%n]=-1,val[x%n]=x,vis[x%n]=1;
q[++up]=y%n,pre[y%n]=-1,val[y%n]=y,vis[y%n]=1;
while(low<=up)
{
int np=q[low++],tmp;
if(np==0)
{
int w=0,len=strlen(s);
for(int k=0;~k;k=pre[k]) ss[w++]=48+val[k];
reverse(ss,ss+w);ss[w]=0;
if(!s[0]||len>w||len==w&&strcmp(ss,s)<0) strcpy(s,ss);
return;
}
if(!vis[tmp=(np*k+x)%n]) q[++up]=tmp,pre[tmp]=np,val[tmp]=x,vis[tmp]=1;
if(!vis[tmp=(np*k+y)%n]) q[++up]=tmp,pre[tmp]=np,val[tmp]=y,vis[tmp]=1;
}
return;
}
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
s[0]=0;
for(int i=1;i<k;i++) bfs(i,i,n,k);
if(!s[0]) for(int i=1;i<k;i++) for(int j=0;j<i;j++) bfs(j,i,n,k);
puts(s);
}
return 0;
}
H
4 substrings problem (HDU
4295)
I
Buildings (HDU
4296)
考虑相连两层a,b（显然不相连的情况相似）：
记tot=w[max(a,b)+1]+……+w[top]：
a在b上面：x=pdv[a]=tot-s[a]
y=pdv[b]=tot+w[a]-s[b]
b在a上面：u=pdv[b]=tot-s[b]
v=pdv[a]=tot+w[b]-s[a]
①s[a]+w[a]>s[b]+w[b]，则有y>v>x与y>u，max(y,x)>max(u,v)，所以b在a上面的放法更优。
②s[a]+w[a]>s[b]+w[b]，则有v>y>u与v>x，max(y,x)<max(u,v)，所以a在b上面的放法更优。
即将k=s[i]+w[i]最大的放在最下面时总PDV最小，而且最优PDV=(w[1]+w[2]+……+w[n])-k。
#include<cstdio>
int main()
{
int n,w,s;
while(scanf("%d",&n)!=EOF)
{
long long k=-1,sum=0;
for(int i=0;i<n;i++) scanf("%d%d",&w,&s),k=w+s>k?w+s:k,sum+=w;
printf("%I64d\n",sum>k?sum-k:0);
}
return 0;
}
J
One and One Story (HDU
4297)