第一题：太鼓达人；BZOJ3033
题意：给出k，求一个最长的M位01串，使其从每一个位置向后走k个得到 的M个k位01串互不相同（最后一个和第一个相邻，即是一个环）。输出 字典序最小的答案。 2 ≤ k ≤ 11。
结论+爆搜；
第二问我们将每个k二进制数看成一个点，在它后面加上0/1就能得 到两个新数，我们从这个数向两个新数连边，于是这就变成了求一个欧 拉回路的问题。显然此题是存在欧拉回路的第一问答案为2的k次方 ,第二问暴力求欧拉回路即可。
发现sjh的注释很详细，所以贿赂搞来了一个满满注释的代码，可以更好地理解；
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+;
template<typename T>inline void read(T &x)
{
x=;
T f=,ch=getchar();
while (!isdigit(ch) && ch^'-') ch=getchar();
if (ch=='-') f=-, ch=getchar();
while (isdigit(ch)) x=(x<<)+(x<<)+(ch^), ch=getchar();
x*=f;
}
int n,t,ans[maxn];
bool used[maxn];
inline bool eular(int x,int k)//x是当前子串的十进制表示，k是当前查询次
{
if (used[x]) return ;
used[x]=,ans[k]=x&;//统计答案，&的规则是：有零则零，否则为一,返回末位数字
if (k==t) return ;//查询结束
if (eular((x<<)&(t-),k+)) return ;
if (eular((x<<|)&(t-),k+)) return ;//将每个二进制数看成一个点，将他前面的数删去，并在它后面加上0/1就能得到两个新数
used[x]=;//回溯，以免影响之后的dfs
return ;
}
int main()
{
read(n);
t=<<n;
printf("%d ",t);
eular(t-,);//从每位走n位子串，可得到的完整子串数量为2^n-2
for (int i=;i<=t;++i)
printf("%d",ans[i]);
return ;
}
意外发现邱神的代码，但没有写题解，所以只能看一下
#include<bits/stdc++.h>
using namespace std;
int read()
{
int a;
cin>>a;
return a;
}
int i,k,m;
struct node
{
int x,deep;
}o[];
bool Orz(node a,node b)
{
return a.deep<b.deep;
}
void dfs(int now,int deep)
{
if(deep==m+)
{
now=now%(m/);
now=now*;
if(now)
return ;
sort(o,o+m,Orz);
for(i=;i<k;i++)
cout<<;
for(i=;i<=m-k;i++)
cout<<o[i].x%; exit() ;
}
//这里应该有一个关于deep和now的if使得dfs停下来并输出
now=now%(m/);
now=now*;
if(!o[now].deep)
{
o[now].deep=deep;
dfs(now,deep+);
o[now].deep=;
}
now++;
if(!o[now].deep)
{
o[now].deep=deep;
dfs(now,deep+);
o[now].deep=;
}
return ;
}
int main()
{
//freopen("123.in","r",stdin);
k=read();m=int(pow(,k*1.0));
cout<<m<<' ';
for(i=;i<m;i++)
o[i].x=i;
o[].deep=;
dfs(,);
}
第二题；poj1386
我们不必要知道每个单词的每个字母，只需要记录首字母和尾字母，所以转换成了一个判断欧拉回路的题目；
首先我们需要知道两个字母知否在一个同一个联通块上，我们可以用并差集来写，然后判断欧拉回路，方法不再陈述；
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<clocale>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<vector>
#include<cwchar>
#include<cwctype>
#define MAX 26
using namespace std;
int out[MAX],in[MAX],flag[MAX],p[MAX],father[MAX];
int Find(int x)
{
if(father[x]!=x)
father[x]=Find(father[x]);
return father[x];
}
void Union(int a,int b)
{
int p=Find(a);
int q=Find(b);
if(p!=q) father[q]=p;
}
int main()
{
int i,k,count,a,b,nc,n;
char str[];
cin>>nc;
while(nc--)
{
for(i=;i<;i++)
father[i]=i;
memset(in,,sizeof(in));
memset(out,,sizeof(out));
memset(flag,,sizeof(flag));
cin>>n;
for(i=;i<=n;i++)
{
cin>>str;
a=str[]-'a';
b=str[strlen(str)-]-'a';
Union(a,b);
in[b]++;
out[a]++;
flag[a]=flag[b]=;
}
count=;
for(i=;i<;i++)
{
father[i]=Find(i);
if(flag[i] && father[i]==i)
count++;
}
if(count>)
{
cout<<"The door cannot be opened."<<endl;
continue;
}
k=;
for(i=;i<;i++)
{
if(flag[i] && in[i]!=out[i])
p[k++]=i;
}
if(k==)
{
cout<<"Ordering is possible."<<endl;
continue;
}
if(k== && ((out[p[]]-in[p[]]== && in[p[]]-out[p[]]==)
|| (out[p[]]-in[p[]]== && in[p[]]-out[p[]]==)) )
{
cout<<"Ordering is possible."<<endl;
continue;
}
cout<<"The door cannot be opened."<<endl;
}
return ;
}
第三题：CF516/B
题目大意：给一个n × m的矩阵，问在其中空白处放置1 × 2, 2 × 1的骨牌的方案 是否存在且唯一。 1 ≤ n, m ≤ 1000；
我们可以用度来表示这个节点当前周围放置的个数；
那么对应度为1的点是一定确定了放置这个点的方式的（显然），对应这个点的四周四个位子中，此时一定只有一个点，那么对应将此处和那个位子直接放置这个1 × 2的形状即可。然后处理完这个点之后，对其他点进行操作，如果再发现了度 为1的点，入队。一直处理下去这样的类似拓扑排序的过程即可。 如果最后还剩下了，说明无法完全覆盖，或者方案不止一个；
所以这个题是拓扑排序的一个拓展；
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue> using namespace std; typedef struct Point
{
int x,y;
}Point; Point a[];
int in[][];
char p[][];
int dx[] = { , , ,-};
int dy[] = { ,-, , };
char ch[] = "><v^";
char st[] = "<>^v";
int m,n;
int k;
bool check(int x,int y) {return x > && x <= m && y > && y <= n;}
void ans(int x,int y)
{
int i,xx,yy,cnt = ;
for(i = ; i < ; ++i)
{
xx = x+dx[i];
yy = y+dy[i];
if(check(xx,yy)&&p[xx][yy]=='.') cnt++;
}
in[x][y]=cnt;
}
bool topo()
{
int i,j,x,y,xx,yy,xxx,yyy,cnt = ;
queue <pair<int,int> > q;
for(j = ; j <k; ++j)
{
x = a[j].x;
y = a[j].y;
if(in[x][y] == )
{
q.push(pair<int,int> (x,y));
in[x][y] = ;
}
}
pair <int,int> m;
while(!q.empty())
{
m = q.front();
q.pop();
x = m.first;
y = m.second;
in[x][y]--;
for(j = ; j < ; ++j)
{
xx = x+dx[j];
yy = y+dy[j];
if(check(xx,yy) && p[xx][yy] == '.')
{
in[xx][yy] = ;
p[xx][yy] = ch[j];
p[x][y] = st[j];
for(int f = ; f < ; ++f)
{
xxx = xx+dx[f];
yyy = yy+dy[f];
if(check(xxx,yyy) && p[xxx][yyy] == '.')
{
ans(xxx,yyy);
if(in[xxx][yyy] == ) q.push(pair<int,int>(xxx,yyy));
}
}
cnt+=;
}
}
}
return cnt == k;
} int main()
{
int i,j;
scanf("%d %d",&m,&n);
k = ;
for(i = ; i <= m; ++i)
{
scanf("%s",p[i]+);
for(j = ; j <= n; ++j)
if(p[i][j] == '.')
{
a[k].x = i;
a[k++].y = j;
in[i][j] = ;
if(check(i-,j) && p[i-][j] == '.')
{
in[i-][j]++;
in[i][j]++;
}
if(check(i,j-) && p[i][j-] == '.')
{
in[i][j-]++;
in[i][j]++;
}
}
} if(topo())
{
for(i = ; i <= m; ++i) printf("%s\n",p[i]+);
}else puts("Not unique"); return ;
}
第四题：poj3169
题目大意：有n头牛，他们按顺序排成了一排，有些牛关系比较好，他们的距 离不能超过某个距离，还有些牛关系不好，他们之间的距离不能小于某 个距离，可能会有多头牛挤在同一位置上，问1号牛和n号牛之间的最大 距离是多少，如果不存在满足条件的排列则输出−1，如果距离无限大则 输出−2。 2 ≤ n ≤ 1000。
查分约束版子题，由题意列出不等式根据三角不等式，建图，跑最短路即可；
题解：令d[i]表示第i头牛的位置，因为牛按顺序排列，则有d[i] ≤ d[i + 1]， 即d[i] − d[i + 1] ≤ 0。 关系不好的牛有d[a] + d ≤ d[b]。 关系好的牛有d[a] + D ≤ d[b], 即d[a] − d[n] ≤ −D 。 跑最短路即可。
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<clocale>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<vector>
#include<cwchar>
#include<cwctype>
const int MAX=1e6+;
const int inf=0x3f3f3f3f;
using namespace std;
inline int read()
{
int x=,f=;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}
while(isdigit(ch)) {x=(x<<)+(x<<)+(ch^);ch=getchar();}
return x*f;
}
int n,x,y,vis[MAX*],dis[MAX*],lin[MAX*],tot,ans[MAX*],a,b,c;
struct gg
{
int y,next,v;
}an[MAX];
void init(int x,int y,int z)
{
an[++tot].y=y;
an[tot].v=z;
an[tot].next=lin[x];
lin[x]=tot;
}
queue<int> q;
int spfa(int s,int n)
{
for (int i=;i<MAX;++i) dis[i]=inf;
memset(ans,,sizeof(ans));
memset(vis,,sizeof(vis));
++ans[s];
dis[s]=;
vis[s]=;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
vis[x]=;
for (int i=lin[x];i;i=an[i].next)
{
int y=an[i].y;
if (dis[y]>dis[x]+an[i].v)
{
dis[y]=dis[x]+an[i].v;
if (!vis[y])
{
vis[y]=,q.push(y);
++ans[y];
if (ans[y]>n) return -;
}
}
}
}
if(dis[n]==inf) return -;
return dis[n];
}
int main()
{
int n=read(),x=read(),y=read();
for (int i=;i<n;++i)
init(i+,i,);
for (int i=;i<=x;++i)
{
int a=read(),b=read(),d=read();
init(a,b,d);
}
for (int i=;i<=y;++i)
{
int a=read(),b=read(),d=read();
init(b,a,-d);
}
cout<<spfa(,n)<<endl;
return ;
}
第五题：poj2983
题目大意：银河系中有n个防御站排成一条直线，给定m条信息，每条信息的 格式如下: P A B X代表A站在B站北方X光年处。 V A B 代表A站在B站北方，而且距离至少为1光年。 问是否存在这样的一个防御战排列满足上述要求，是输出Reliable，否输 出Unreliable。
dist[A] − dist[B] ≥ X，表示A在B北边至少X光年位置。变形为： dist[B] <= dist[A] − X;所以A指向B有条权值为-X的边。 对于A − B = X，建两条边dist[B] ≤ dist[A] − X， dist[A] ≤ dist[B] + X。
SPFA存在负权环则说明不符合实际情况。
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cstdio>
#include <set>
#include <math.h>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <map>
#include <cctype>
#define INF 0x3f3f3f3f
#define MAXN 1000005
#define Mod 1000000007
using namespace std;
struct Edge
{
int v,w,next;
};
Edge edge[MAXN<<];
int head[MAXN],n,m,e,vis[MAXN],dis[MAXN];
int p[MAXN];
void add(int u,int v,int w)
{
edge[e].v=v;
edge[e].w=w;
edge[e].next=head[u];
head[u]=e;
e++;
}
bool spfa(int u)
{
memset(vis,,sizeof(vis));
for(int i=;i<=n;++i)
dis[i]=-INF;
dis[u]=;
queue<int> q;
q.push(u);
while(!q.empty())
{
u=q.front();
q.pop();
vis[u]=;
p[u]++;
if(p[u]>n)
return false;
for(int i=head[u];i!=-;i=edge[i].next)
{
int v=edge[i].v,w=edge[i].w;
if(w+dis[u]>dis[v])
{
dis[v]=w+dis[u];
if(!vis[v])
{
vis[v]=;
q.push(v);
}
}
}
}
return true;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
e=;
memset(head,-,sizeof(head));
memset(p,,sizeof(p));
for(int i=;i<m;++i)
{
int a,b,c;
char op;
cin>>op;
if(op=='P')
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,-c);
}
else
{
scanf("%d%d",&a,&b);
add(a,b,);
}
}
for(int i=;i<=n;++i)
add(,i,);
if(spfa())
printf("Reliable\n");
else
printf("Unreliable\n");
}
return ;
}
第六题：hdu3440
题目大意：T组数据，有n栋房子在一条直线上，给出每栋房子的高度和开始时 的相对位置，可以移动一些房子，但不能改变这些房子的相对位置，现 在从最矮的房子开始，每次跳至第一个比它高的房子，经过n − 1跳到达 最高的房子。而且每次跳跃的水平距离最大是D，房子不能在同一位置， 只能在整点位置。问最矮的房子和最高的房子之间的最大距离可以是多 少？如果不能从最矮的房子到达最高的房子则输出−1。 1 ≤ T ≤ 500, 1 ≤ N ≤ 500。
令d[i]表示第i栋房子与第一栋房子之间的最大距离，那么我们要求的就是的d[n]。 首先每栋房子之间的相对位置已经确定且不能在同一位置，那么d[i + 1]>d[i]，即d[i + 1] − d[i] ≥ 1,即d[i] − d[i + 1] ≤ −1。 还有一个条件是相邻两个要跳跃的距离不可以大于D，可以写出另一个方程。有一点小问题就是建边的方向和跳跃的方向不同，我们要保证是向一个方向建图的。 若从左到右建边，如果1在n的左面就从1到n跑SPFA，反之则从n到1跑最短路了。
暂无代码；
第七题：poj1275
题解：每天的工作情况都是一样的，我们只需要求出一天的即可。根据题 意，令s[i]为一天内前i + 1个小时录用的人数。 ◆ 如果i ≥ 7,则s[i] − s[i − 8] ≥ R[i] ◆ 如果0 ≤ i < 7，则可以推出s[23] − s[i + 16] + s[i] ≥ R[i] ◆ 同时每个时刻录用的人数有个上限，假设第i时刻最多可以 录用的人数为b[i],则对于每一 个i有0 ≤ s[i] − s[i − 1] ≤ b[i]。 第二个不等式中包含3个s数组的变量，这该怎么建图呢？ 枚举s[23]，那么这个量就是已知的了，因此不等式可以变 为s[i] − s[i + 16] ≥ R[i] − s[23]。 既然s[23]是枚举的一天的录用人数的最小数目，我们建图之后求出 的s[23]也应该为枚举的那个值。单调性，二分。
暂无代码;