Fox Ciel is going to publish a paper on FOCS (Foxes Operated Computer Systems, pronounce: "Fox"). She heard a rumor: the authors list on the paper is always sorted in the lexicographical order.
After checking some examples, she found out that sometimes it wasn't true. On some papers authors' names weren't sorted inlexicographical order in normal sense. But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical!
She wants to know, if there exists an order of letters in Latin alphabet such that the names on the paper she is submitting are following in the lexicographical order. If so, you should find out any such order.
Lexicographical order is defined in following way. When we compare s and t, first we find the leftmost position with differing characters: si ≠ ti. If there is no such position (i. e. s is a prefix of t or vice versa) the shortest string is less. Otherwise, we compare characters si and ti according to their order in alphabet.
The first line contains an integer n (1 ≤ n ≤ 100): number of names.
Each of the following n lines contain one string namei (1 ≤ |namei| ≤ 100), the i-th name. Each name contains only lowercase Latin letters. All names are different.
If there exists such order of letters that the given names are sorted lexicographically, output any such order as a permutation of characters 'a'–'z' (i. e. first output the first letter of the modified alphabet, then the second, and so on).
Otherwise output a single word "Impossible" (without quotes).
3 rivest shamir adleman
bcdefghijklmnopqrsatuvwxyz
10 tourist petr wjmzbmr yeputons vepifanov scottwu oooooooooooooooo subscriber rowdark tankengineer
Impossible
10 petr egor endagorion feferivan ilovetanyaromanova kostka dmitriyh maratsnowbear bredorjaguarturnik cgyforever
aghjlnopefikdmbcqrstuvwxyz
7 car care careful carefully becarefuldontforgetsomething otherwiseyouwillbehacked goodluck
acbdefhijklmnogpqrstuvwxyz
拓扑排序。
对于有大小要求的字母从小的向大的连一条有向边。
只要拓扑排序之后所有点度数为0，那么就是可行的；否则存在环，不可行。
这道题有个细节是：
要处理类似于
abc
ab
这种情况，显然是无解的，注意特判一下。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
using namespace std;
char s[105][105];
queue<int> q;
int du[30],v[30],vv[30],ans[30],n,len[105],tot,h[30];
struct edge
{
int y,ne;
}e[30000];
void Addedge(int x,int y)
{
v[x]=1,v[y]=1;
du[y]++;
e[++tot].y=y;
e[tot].ne=h[x];
h[x]=tot;
}
void Solve(int l,int r,int k)
{
if (l==r) return;
int L=l,now=l+1,f=0;
if (len[l]<k) L++,f=1;
while (now<=r)
{
if (len[now]<k)
{
du[1]=1000;
return;
}
if ((now==l+1&&f)||s[now][k]==s[L][k]) now++;
else
{
int R=now-1;
if (L!=now)
{
Addedge(s[L][k]-'a'+1,s[now][k]-'a'+1);
Solve(L,R,k+1);
}
L=now;
now++;
}
}
if (L!=r) Solve(L,r,k+1);
}
int Topsort()
{
int now=0;
for (int i=1;i<=26;i++)
if (v[i]&&!du[i]) q.push(i);
while (!q.empty())
{
int x=q.front();
q.pop();
ans[++now]=x;
vv[x]=1;
for (int i=h[x];i;i=e[i].ne)
{
int y=e[i].y;
du[y]--;
if (!du[y]) q.push(y);
}
}
for (int i=1;i<=26;i++)
if (du[i]) return 0;
for (int i=1;i<=26;i++)
if (!vv[i]) ans[++now]=i;
return true;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%s",s[i]),len[i]=strlen(s[i])-1;
for (int i=1;i<=n;i++)
for (int j=len[i]+1;j<=103;j++)
s[i][j]='z'+10;
Solve(1,n,0);
if (Topsort())
{
for (int i=1;i<=26;i++)
cout<<(char)(ans[i]+'a'-1);
cout<<endl;
}
else
{
puts("Impossible");
}
return 0;
}
Fox Ciel is playing a game. In this game there is an infinite long tape with cells indexed by integers (positive, negative and zero). At the beginning she is standing at the cell 0.
There are also n cards, each card has 2 attributes: length li and cost ci. If she pays ci dollars then she can apply i-th card. After applying i-th card she becomes able to make jumps of length li, i. e. from cell x to cell (x - li) or cell (x + li).
She wants to be able to jump to any cell on the tape (possibly, visiting some intermediate cells). For achieving this goal, she wants to buy some cards, paying as little money as possible.
If this is possible, calculate the minimal cost.
The first line contains an integer n (1 ≤ n ≤ 300), number of cards.
The second line contains n numbers li (1 ≤ li ≤ 109), the jump lengths of cards.
The third line contains n numbers ci (1 ≤ ci ≤ 105), the costs of cards.
If it is impossible to buy some cards and become able to jump to any cell, output -1. Otherwise output the minimal cost of buying such set of cards.
3 100 99 9900 1 1 1
2
5 10 20 30 40 50 1 1 1 1 1
-1
7 15015 10010 6006 4290 2730 2310 1 1 1 1 1 1 1 10
6
8 4264 4921 6321 6984 2316 8432 6120 1026 4264 4921 6321 6984 2316 8432 6120 1026
7237
首先可以明确一点：能到达所有点也就是说通过所选卡片拼拼凑凑能够拼出1来，什么情况能拼出1来呢？
所有数的gcd为1！！
为什么呢？
求gcd有一个方法是辗转相减吧，那么gcd为1说明通过辗转相减可以得到1。。因此就是gcd为1！
（那么如果要能拼凑出x来，就要让gcd为x的因数。。）
接下来就可以dp了，用map可以轻松水过。。
dp[x]表示最大公约数为x时，至少要花dp[x]的钱。
扫描一次，判断dp[1]是否存在即可。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#define M 300+5
#include <map>
#define mp make_pair
using namespace std;
int n,c[M],l[M];
map<int,int> dp;
map<int,int>::iterator it;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&l[i]);
for (int i=1;i<=n;i++)
scanf("%d",&c[i]);
for (int i=1;i<=n;i++)
{
for (it=dp.begin();it!=dp.end();it++)
{
int x=it->first;
x=__gcd(x,l[i]);
if (!dp[x])
dp[x]=it->second+c[i];
else dp[x]=min(dp[x],it->second+c[i]);
}
int x=l[i];
if (!dp[x])
dp[x]=c[i];
else dp[x]=min(dp[x],c[i]);
}
if (!dp[1]) puts("-1");
else printf("%d\n",dp[1]);
return 0;
}
Fox Ciel is participating in a party in Prime Kingdom. There are n foxes there (include Fox Ciel). The i-th fox is ai years old.
They will have dinner around some round tables. You want to distribute foxes such that:
If k foxes f1, f2, ..., fk are sitting around table in clockwise order, then for 1 ≤ i ≤ k - 1: fi and fi + 1 are adjacent, and f1 and fk are also adjacent.
If it is possible to distribute the foxes in the desired manner, find out a way to do that.
The first line contains single integer n (3 ≤ n ≤ 200): the number of foxes in this party.
The second line contains n integers ai (2 ≤ ai ≤ 104).
If it is impossible to do this, output "Impossible".
Otherwise, in the first line output an integer m (
): the number of tables.
Then output m lines, each line should start with an integer k -=– the number of foxes around that table, and then k numbers — indices of fox sitting around that table in clockwise order.
If there are several possible arrangements, output any of them.
4 3 4 8 9
1 4 1 2 4 3
5 2 2 2 2 2
Impossible
12 2 3 4 5 6 7 8 9 10 11 12 13
1 12 1 2 3 6 5 12 9 8 7 10 11 4
24 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
3 6 1 2 3 6 5 4 10 7 8 9 12 15 14 13 16 11 10 8 17 18 23 22 19 20 21 24
In example 1, they can sit around one table, their ages are: 3-8-9-4, adjacent sums are: 11, 17, 13 and 7, all those integers are primes.
In example 2, it is not possible: the sum of 2+2 = 4 is not a prime number.
这不是网络流24题里面的魔术球问题吗？？
不是！！
这道题要求队首和队尾之和也是质数，而魔术球问题不要求，这就导致两者的建图几乎完全不同。
注意题目中说ai>=2，那么一个桌子上的奇数与偶数的数量是相同的：
一个偶数的左右必然都是奇数；
一个奇数左右必然都是偶数。
建图方法是：
s与奇数连流量为2的边，偶数与t连流量为2的边；
奇数与偶数之和是质数的连流量为1的边。
最大流为n则必有解，判断哪条边有流量输出答案即可。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <queue>
#define M 500
#define inf 0x3f3f3f3f
using namespace std;
struct data
{
int p,v;
}a[M],o[M];
struct edge
{
int from,to,cap,flow,ne;
}E[200005];
int ok[100005],st,cnt,tot=1,s,t,r[M][3],cur[M],v[M],d[M],h[M],p[M*20],now[M][M],n;
void Addedge(int from,int to,int cap)
{
E[++tot]=(edge){from,to,cap,0,h[from]};
h[from]=tot;
E[++tot]=(edge){to,from,0,0,h[to]};
h[to]=tot;
}
void Prepare()
{
for (int i=2;i<=100000;i++)
ok[i]=1;
for (int i=2;i<=100000;i++)
if (ok[i])
{
p[++cnt]=i;
for (int j=i*2;j<=100000;j+=i)
ok[j]=0;
}
}
bool Judge(int x)
{
for (int i=1;i<=cnt;i++)
{
if (x==p[i]) return true;
if (p[i]*p[i]>x) return true;
if (x%p[i]==0) return false;
}
return true;
}
bool bfs()
{
for (int i=s;i<=t;i++)
d[i]=0,v[i]=0;
v[s]=1;
queue<int> q;
q.push(s);
d[s]=0;
while (!q.empty())
{
int x=q.front();
q.pop();
for (int i=h[x];i;i=E[i].ne)
{
edge e=E[i];
if (!v[e.to]&&e.cap>e.flow)
{
v[e.to]=1;
d[e.to]=d[x]+1;
q.push(e.to);
}
}
}
return v[t];
}
int dfs(int x,int a)
{
if (x==t||!a) return a;
int f,flow=0;
for (int &i=cur[x];i;i=E[i].ne)
{
edge &e=E[i];
if (d[x]+1!=d[e.to]) continue;
f=dfs(e.to,min(a,e.cap-e.flow));
if (f>0)
{
e.flow+=f;
E[i^1].flow-=f;
a-=f;
flow+=f;
if (a==0) break;
}
}
return flow;
}
int dinic()
{
int flow=0;
while (bfs())
{
for (int i=s;i<=t;i++)
cur[i]=h[i];
flow+=dfs(s,inf);
}
return flow;
}
void Print()
{
memset(v,0,sizeof(v));
for (int i=st;i<=tot;i++)
{
if (E[i].from>E[i].to) continue;
if (E[i].flow)
{
int x=E[i].from,y=E[i].to;
if (r[x][0]) r[x][1]=y;
else r[x][0]=y;
if (r[y][0]) r[y][1]=x;
else r[y][0]=x;
}
}
int num=0;
for (int i=1;i<=n/2;i++)
{
if (v[i]) continue;
num++;
int y=i,x=r[i][0];
now[num][1]=y,now[num][2]=x;
now[num][0]=2;
v[x]=v[y]=1;
while (now[num][now[num][0]]!=r[i][1])
{
if (r[x][0]==y) now[num][++now[num][0]]=r[x][1];
else now[num][++now[num][0]]=r[x][0];
y=now[num][now[num][0]];
if (r[y][0]==x) x=r[y][1];
else x=r[y][0];
v[x]=v[y]=1;
now[num][++now[num][0]]=x;
}
}
cout<<num<<endl;
for (int i=1;i<=num;i++)
{
cout<<now[i][0];
for (int j=1;j<=now[i][0];j++)
cout<<" "<<o[now[i][j]].p;
cout<<endl;
}
}
int main()
{
Prepare();
scanf("%d",&n);
int k=n/2,co=0,ce=0;
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i].v);
a[i].p=i;
if (a[i].v&1) o[++co]=a[i];
else ce++,o[ce+k]=a[i];
}
if (ce!=co)
{
puts("Impossible");
return 0;
}
s=0,t=n+1;
for (int i=s;i<=t;i++)
h[i]=0;
for (int i=1;i<=n;i++)
{
if (i<=k) Addedge(s,i,2);
else Addedge(i,t,2);
}
st=tot+1;
for (int i=1;i<=k;i++)
{
for (int j=k+1;j<=n;j++)
if (Judge(o[i].v+o[j].v)) Addedge(i,j,1);
}
if (dinic()==n)
Print();
else
puts("Impossible");
return 0;
}
1.B题把题目转化为gcd问题是关键：如果几个数的gcd为x，那么通过加加减减一定可以拼凑出x来！！
2.C又是因为定式思维导致没有想到建图方法。。看起来相似的题目做法很可能完全不同！
这道题建图的关键在于：
奇数左右必然都是偶数；偶数左右必然都是奇数。
因此都是流量为2。