今天做了一下zoj的月赛。再次被虐。。只做出几道题目。
麻将虽然在天津遇到过，但这次还是被虐，等考试复习完了，得好好反思了。
差分约束,这道题目是一道差分约束的题目，其实很典型，一开始没有想清楚，当做上下界的网络流做了两个小时。。。大把大把的时间。
约束条件 :f[i] 表示前i块石头的能量总和。
f[R]-f[L-1]>=A
f[R]-f[L-1]<=B
f[i]-f[i-1]<=10000
f[i]-f[i-1]>=-10000
用SPFA跑一遍 dis[i]-dis[i-1]就是我们要的答案：
简单水题
注意点是对子不能重复。
状态压缩DP，一开始M的大小没看清楚数组只开到1<<10的大小，后来改成1<<22之后就A掉了，中途不断改代码，改的稀烂。。。
代码（写的很挫，写代码的时候改动很多）
C
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define MAXN 1100
#define INF 10000000
struct node
{
int to;
int dis;
};
bool in[MAXN];
int s[MAXN];
int cnt[MAXN];
vector<node> g[MAXN];
int n,m,dis[MAXN];
bool spfa(int s)
{
queue<int> q;
for(int i=0;i<=n;i++)
{
cnt[i]=0;
dis[i]=INF;
in[i]=false;
}
dis[s]=0;
in[s]=true;
q.push(s);
cnt[s]++;
while(!q.empty())
{
int tag=q.front();
in[tag]=false;
q.pop();
for(int i=0;i<g[tag].size();i++)
{
int j=g[tag][i].to;
if(dis[tag]+g[tag][i].dis<dis[j])
{
dis[j]=dis[tag]+g[tag][i].dis;
if(!in[j])
{
q.push(j);
in[j]=true;
cnt[j]++;
if(cnt[j]>=n+1)
return false;
}
}
}
}
return true;
}
void solve()
{
int L,R,A,B;
node tmp;
for(int i=0;i<=n;i++)
g[i].clear();
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&L,&R,&A,&B);
tmp.to=R;
tmp.dis=B;
g[L-1].push_back(tmp);
tmp.to=L-1;
tmp.dis=-A;
g[R].push_back(tmp);
}
for(int i=1;i<=n;i++)
{
tmp.to=i-1;
tmp.dis=10000;
g[i].push_back(tmp);
tmp.to=i;
tmp.dis=10000;
g[i-1].push_back(tmp);
}
if(spfa(0))
{
for(int i=1;i<=n;i++)
{
if(i!=1)
printf(" %d",dis[i]-(dis[i-1]));
else
printf("%d",dis[i]-(dis[i-1]));
}
printf("\n");
}
else
printf("The spacecraft is broken!\n");
}
int main()
{
while(~scanf("%d%d",&n,&m))
solve();
return 0;
}
F
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iterator>
using namespace std;
#define INF 0x3f3f3f3f
int mj[20];
char str[100];
bool cmp(int a,int b)
{
return a<b;
}
bool SevenPairs()
{
for(int i=0;i<7;i++)
{
if(mj[i*2]!=mj[i*2+1]) return false;
if(i!=0 )
if(mj[i*2]==mj[i*2-1]) return false;
}
return true;
}
bool ThirteenOrphans()
{
vector<int> ve;
ve.assign(mj,mj+14);
vector<int>::iterator it = unique(ve.begin(),ve.end());
ve.erase(it, ve.end());
if(ve.size()==14) return false;
for(int i=0;i<3;i++)
{
if(ve[i*2+1]-ve[i*2]!=8 && ve[i*2]==i*10+1)
return false;
}
if(ve[6]!=31) return false;
for(int i=7;i<13;i++)
{
if(ve[i]!=ve[i-1]+1) return false;
}
return true;
}
void solve()
{
for(int i=0;i<14;i++)
{
mj[i]=str[i*2]-'0';
switch(str[i*2+1])
{
case 's': mj[i]+=10;break;
case 'm': mj[i]+=20;break;
case 'z': mj[i]+=30;break;
}
}
sort(mj,mj+14,cmp);
if(SevenPairs())
{
printf("Seven Pairs\n");
return;
}
if(ThirteenOrphans())
{
printf("Thirteen Orphans\n");
return;
}
printf("Neither!\n");
}
int main()
{
while(~scanf("%s",&str))
solve();
return 0;
}
J
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
#define INF 0x3fffff
int dp[1<<22];
int state[1<<22],top;
char tmp[200],str[200];
int n,m;
void solve()
{
char s;
scanf("%s",tmp);
scanf("%d",&m);
for(int i=1;i<=m;i++)
str[i]='.';
for(int i=1;i<=strlen(tmp);i++)
str[i+m]=tmp[i-1];
for(int i=strlen(tmp)+m+1;i<=strlen(tmp)+m+m;i++)
str[i]='.';
top=0;
for(int i=1;i<=strlen(tmp)+m;i++)
{
int ss=0;
for(int j=0;j<m;j++)
{
if(str[i+j]=='*')
ss|=(1<<j);
}
state[top++]=ss;
}
for(int i=strlen(tmp)+m+m;i>m;i--)
{
int ss=0;
for(int j=0;j<m;j++)
{
if(str[i-j]=='*')
ss|=(1<<j);
}
state[top++]=ss;
}
for(int s=0;s<(1<<m);s++)
dp[s]=INF;
dp[0]=0;
for(int s=0;s<(1<<m);s++)
{
if(dp[s]==INF) continue;
for(int k=0;k<top;k++)
dp[s|state[k]]=min(dp[s]+1,dp[s|state[k]]);
}
if(dp[(1<<m)-1]==INF)
printf("-1\n");
else
printf("%d\n",dp[(1<<m)-1]);
}
int main()
{
while(~scanf("%d",&n))
solve();
return 0;
}