o(╥﹏╥)o
页面找不到了
推荐阅读：有所作为是生活中的最高境界。
BZOJ 1797([Ahoi2009]Mincut 最小割-最小割的可行边与必行边)
Description
A,B两个国家正在交战，其中A国的物资运输网中有N个中转站，M条单向道路。设其中第i (1≤i≤M)条道路连接了vi,ui两个中转站，那么中转站vi可以通过该道路到达ui中转站，如果切断这条道路，需要代价ci。现在B国想找出一个路径切断方案，使中转站s不能到达中转站t，并且切断路径的代价之和最小。 小可可一眼就看出，这是一个求最小割的问题。但爱思考的小可可并不局限于此。现在他对每条单向道路提出两个问题： 问题一：是否存在一个最小代价路径切断方案，其中该道路被切断？ 问题二：是否对任何一个最小代价路径切断方案，都有该道路被切断？ 现在请你回答这两个问题。
第一行有4个正整数，依次为N,M,s和t。第2行到第(M+1)行每行3个正 整数v,u,c表示v中转站到u中转站之间有单向道路相连，单向道路的起点是v， 终点是u,切断它的代价是c(1≤c≤100000)。 注意:两个中转站之间可能有多条道路直接相连。 同一行相邻两数之间可能有一个或多个空格。
对每条单向边，按输入顺序，依次输出一行，包含两个非0即1的整数，分 别表示对问题一和问题二的回答(其中输出1表示是，输出0表示否)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。
Sample Input
Sample Output
设第(i+1)行输入的边为i号边，那么{1,2},{6,7},{2,4,6}是仅有的三个最小代价切割方案。它们的并是{1,2,4,6,7}，交是 。 【数据规模和约定】 测试数据规模如下表所示 数据编号 N M 数据编号 N M 1 10 50 6
2 20 200 7
0 0 0 60000
新加数据一组，可能会卡掉从前可以过的程序。
同之前的那篇题解
最小割的可行边的充分必要条件：网络流中满流且残余网络中边的2点不在一个scc中。
必行边：是可行边，且残余网络与s，t点分别在一个联通块
#include &iostream&
#include &cmath&
#include &algorithm&
#include &cstdio&
#include &cstring&
#include &string&
#include &vector&
#include &map&
#include &functional&
#include &cstdlib&
#include &queue&
#include &stack&
using namespace std;
#define For(i,n) for(int i=1;i&=n;i++)
#define Fork(i,k,n) for(int i=k;i&=n;i++)
#define Rep(i,n) for(int i=0;i&n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define ForkD(i,k,n) for(int i=n;i&=k;i--)
#define RepD(i,n) for(int i=n;i&=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])
#define Lson (o&&1)
#define Rson ((o&&1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF ()
#define F ()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector&int&
#define pi pair&int,int&
#define SI(a) ((a).size())
typedef long long
typedef unsigned long long
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
#define MAXN ()
#define MAXM ()
class tar{
vi G[MAXN],G2[MAXN];
int pre[MAXN],lowlink[MAXN],sccno[MAXN],dfs_clock,scc_
stack&int& S;
void dfs(int u) {
pre[u] = lowlink[u] = ++dfs_
S.push(u);
int sz=SI(G[u]);
Rep(i,sz) {
int v=G[u][i];
if (!pre[v]) {
lowlink[u]=min(lowlink[u],lowlink[v]);
} else if (!sccno[v]) {
lowlink[u]=min(lowlink[u],pre[v]);
if (lowlink[u]==pre[u]) {
scc_cnt++;
while(1) {
int x=S.top();S.pop();
sccno[x]=scc_
if (x==u) break;
void find_scc(int n) {
dfs_clock = scc_cnt = 0;
MEM(sccno)
Rep(i,n) if (!pre[i]) dfs(i);
void mem(int n) {
Rep(i,n) G[i].clear(),G2[i].clear();
class Max_flow
int q[MAXN];
ll weight[MAXM];
int edge[MAXM],Next[MAXM],Pre[MAXN],
void addedge(int u,int v,int w)
edge[++size]=v;
weight[size]=w;
Next[size]=Pre[u];
void addedge2(int u,int v,int w){addedge(u,v,w),addedge(v,u,0);}
bool b[MAXN];
ll d[MAXN];
bool SPFA(int s,int t)
d[q[1]=s]=0;b[s]=1;
int head=1,tail=1;
while (head&=tail)
int now=q[head++];
int &v=edge[p];
if (weight[p]&&!b[v])
d[v]=d[now]+1;
b[v]=1,q[++tail]=v;
return b[t];
int iter[MAXN];
int dfs(int x,ll f)
if (x==t) return
Forpiter(x)
int v=edge[p];
if (weight[p]&&d[x]&d[v])
int nowflow=dfs(v,min(weight[p],f));
if (nowflow)
weight[p]-=
weight[p^1]+=
ll max_flow(int s,int t)
(*this).t=t;
ll flow=0;
while(SPFA(s,t))
For(i,n) iter[i]=Pre[i];
while (f=dfs(s,INF))
void mem(int n)
(*this).n=n;
void init(int n) {
For(i,n) {
int v=edge[p];
if (!weight[p]) {
else S2.G[i-1].pb(v-1),S2.G2[i-1].pb(p);
int main() {
int n,m,s,t;
n=read(),m=read(),s=read(),t=read();
For(i,m) {
int u=read(),v=read(),w=read();
S.addedge2(u,v,w);
e[i].u=u,e[i].v=v;
ll p=S.max_flow(s,t);
S.init(n);
S2.find_scc(n);
For(i,m) {
e[i].u--,e[i].v--;
if (S.weight[i*2]) puts("0 0");
else if (S2.sccno[e[i].u]==S2.sccno[s] && S2.sccno[e[i].v]==S2.sccno[t]) puts("1 1");
else if (S2.sccno[e[i].u]!=S2.sccno[e[i].v]) puts("1 0");
else puts("0 0");
S2.mem(n);
没有更多推荐了，有所作为是生活中的最高境界。
HDU 5334(Virtual Participation-(A+C+1)(B+C+1)=K+(1+C)^2-C)
Virtual Participation
Time Limit:
MS (Java/Others)
Memory Limit:
K (Java/Others)
Total Submission(s): 886
Accepted Submission(s): 257Special JudgeProblem Description
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he asks rikka to have some practice on codeforces. Then she opens the problem B:
Given an integer K,
she needs to come up with an sequence of integers
satisfying that the number of different continuous subsequence of
is equal to k.
Two continuous subsequences a, b
are different if and only if one of the following conditions is satisfied:
1. The length of a
is not equal to the length of b.
2. There is at least one t
that at≠bt,
means the t-th
element of a
means the t-th
element of b.
Unfortunately, it is too difficult for Rikka. Can you help her?
There are at most 20 testcases，each testcase only contains a single integerK (1≤K≤109)
For each testcase print two lines.
The first line contains one integers n (n≤min(K,105)).
The second line contains n
space-separated integer Ai (1≤Ai≤n)
- the sequence you find.
Sample Input
Sample Output
We have carefully selected several similar problems for you:
假设答案只有A个1，B个2，C个3
则原题要找A+B+C&=Min(K,10^5) 且 A+B+C+AB+BC+AC=K 的解
右边方程移项得，(A+C+1)(B+C+1)=K+(1+C)^2-C
#include&cstdio&
#include&cstring&
#include&cstdlib&
#include&algorithm&
#include&functional&
#include&iostream&
#include&cmath&
#include&cctype&
#include&ctime&
#define For(i,n) for(int i=1;i&=n;i++)
#define Fork(i,k,n) for(int i=k;i&=n;i++)
#define Rep(i,n) for(int i=0;i&n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i&=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x&&1)
#define Rson ((x&&1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF ()
#define F ()
#define MAXN ()
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
void work(ll k,ll &A,ll &B,ll &C)
int K2=k+(1+C)*(1+C)-C;
for(ll x=(ll)(sqrt(K2));x&=C+1;x--)
if (K2%x==0) {
A=x-C-1,B=K2/x-C-1;
if (A+B+C&100000)
int main()
// freopen("H.in","r",stdin);
while (cin&&k) {
if (k==1) {
puts("1");
puts("1");
} else if (k==2) {
puts("2");
puts("1 1");
} else if (k&=100000){
printf("%d\n",k);
For(i,k-1) printf("1 ");printf("1\n");
ll A,B,C=0;
work(k,A,B,C);
printf("%d\n",A+B+C);
bool flag=0;
if (!flag) flag=1;else printf(" ");
printf("1");
if (!flag) flag=1;else printf(" ");
printf("2");
if (!flag) flag=1;else printf(" ");
printf("3");
}printf("\n");
没有更多推荐了，有所作为是生活中的最高境界。
CF497D(Gears-线段与圆相交)
memory limit per test
256 megabytes
standard input
standard output
There are two polygons on the plane,
and . Polygon
around point , and polygon
rotates around point .
Each polygon rotates with the constant rotational speed in the clockwise direction around its point, the rotational speed values of the polygons' rotation are equal.
Your task is to determine if there will be a collision between polygons. A collision is a situation when the polygons have at least
one common point.
It is guaranteed that at the moment
the polygons
not intersect and no polygon is fully contained inside another one.
Note that:
The first line contains space-separated coordinates of point .
The second line contains a single integer
the number of vertices of polygon .
Each of the next
lines contains two space-separated integers — the coordinates of the corresponding vertex of polygon .
The next line is empty.
Then follow space-separated coordinates of point .
The next line contains a single integer
the number of vertices of polygon . Next
contain the coordinates of the vertices of the polygon .
The vertices of both polygons are listed in the counterclockwise order. Coordinates of all points are integers, their absolute values don't exceed .
Print "YES", if the collision takes place and "NO" otherwise
(don't print the quotes).
Sample test(s)
A polygon is a closed polyline that doesn't intersect itself and doesn't touch itself.
Picture to the first sample:
假定P和多边形A不动，则Q点绕P逆时针转动，
设Q为多边形B上一点，若B不绕Q转，则B绕P逆时针转，
但B绕Q顺时针转，
设B‘为Q上一点，向量QB’绕P逆时针转，
额外加上B‘绕Q顺时针转，则向量QB’不变，Q，B‘相对静止 =》Q,B相对静止
此时Q的运动轨迹为圆，B’的运动轨迹为圆加上一个定值向量，位移了的圆
而B可能出现的位置就是圆心加上一个定值向量的圆的集合，即圆心可以在某个多边形上移动，半径恒=|PQ| 的圆（镂空）扫过的面积
另一点：2个之前不相交的多边形相撞，必有某一时刻一个多边形的端点和另一个多边形的线段（含端点）重合
所有只要判断P交Q和Q交P的情况就行了
#include&cstdio&
#include&cstring&
#include&cstdlib&
#include&algorithm&
#include&functional&
#include&iostream&
#include&cmath&
#include&cctype&
#include&ctime&
#define For(i,n) for(int i=1;i&=n;i++)
#define Fork(i,k,n) for(int i=k;i&=n;i++)
#define Rep(i,n) for(int i=0;i&n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i&=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x&&1)
#define Rson ((x&&1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF ()
#define F ()
#define MAXN (1000+10)
#define eps (1e-5)
long long mul(long long a,long long b){return (a*b)%F;}
long long add(long long a,long long b){return (a+b)%F;}
long long sub(long long a,long long b){return (a-b+(a-b)/F*F+F)%F;}
P(int _x,int _y):x(_x),y(_y){}
P(P A,P B):x(B.x-A.x),y(B.y-A.y){}
friend P operator+(P A,P B){return P(A.x+B.x,A.y+B.y);}
friend double operator*(P A,P B){return A.x*B.x+A.y*B.y;}
void print(){cout&&x&&' '&&y&& }
}p,q,a[MAXN],b[MAXN];
double sqr(double x){return x*x;}
double dis(P A,P B)
return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));
S(P _A,P _B):A(_A),B(_B){}
C(P _O,double _r):O(_O),r(_r){}
bool is_cross(S p)
double dis1=dis(p.A,O),dis2=dis(p.B,O);
if (max(dis1,dis2)&r-eps) return 0; //端点在园内
cout&&dis1&&' '&&dis2&&' '&&r&&
if (abs(dis1-r)&eps||abs(dis2-r)&eps||(dis1-r)*(dis2-r)&0) return 1; //有端点在圆上||端点一里一外
P A=p.A,B=p.B;
if (abs((B.y-A.y)*O.x-(B.x-A.x)*O.y+A.y*B.x-A.x*B.y)&=r*dis(A,B)+eps)
//端点在园外
// cout&&abs((B.y-A.y)*O.x-(B.x-A.x)*O.y+A.y*B.x-A.x*B.y)/dis(A,B)&&
// O.print();A.print();B.print();cout&&r&&
// cout&&P(B,A)*P(B,O)&&' '&&P(A,B)*P(A,O)&&
if (P(B,A)*P(B,O)&=0&&P(A,B)*P(A,O)&=0) //线段的距离=直线的距离，等价于△OAB是锐角△
bool side_to_dot(P p,P a[],int n,P q,P b[],int m) //side_to_dot
double r=dis(p,q);
C c=C(p+P(q,b[i]),r);
if (c.is_cross(S(a[j],a[j+1])))
int main()
// freopen("CF497D.in","r",stdin);
// freopen(".out","w",stdout);
scanf("%d%d",&p.x,&p.y);
scanf("%d",&n);
scanf("%d%d",&a[i].x,&a[i].y); a[n+1]=a[1];
scanf("%d%d",&q.x,&q.y);
scanf("%d",&m);
scanf("%d%d",&b[i].x,&b[i].y); b[m+1]=b[1];
if (side_to_dot(p,a,n,q,b,m)||side_to_dot(q,b,m,p,a,n))
cout&&"YES"&&
cout&&"NO"&&
没有更多推荐了，有所作为是生活中的最高境界。
CF 582A(GCD Table-贪心)
已知一个序列，两两gcd得到一张表 （图为4,3,6,2)
现在给出表中所有项（不按顺序），给出原序列一个合法解
预处理，把gcd表存为i的倍数在表中出现hi次，显然hi是完全平方数，取根号得到序列中i的倍数出现几次
贪心取最大的那个，把它从gcd表中删去，再取..
#include&cstdio&
#include&cstring&
#include&cstdlib&
#include&algorithm&
#include&functional&
#include&iostream&
#include&cmath&
#include&cctype&
#include&ctime&
#include&map&
using namespace std;
#define For(i,n) for(int i=1;i&=n;i++)
#define Fork(i,k,n) for(int i=k;i&=n;i++)
#define Rep(i,n) for(int i=0;i&n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define RepD(i,n) for(int i=n;i&=0;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x&&1)
#define Rson ((x&&1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF ()
#define F ()
#define MAXN ()
typedef long long
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int n,a[MAXN];
map&int,int&
map&int,int&::
int ans[MAXN]={0},siz=0;
void ad(int x)
it=h.find(x);
if (it!=h.end()) it-&second++;
else h[x]=1;
int main()
freopen("data.in","r",stdin);
For(i,n*n) scanf("%d",&a[i]);
bool flag=0;
For(i,n*n-1)
if (a[i]!=a[i+1]) {
flag=1;break;
if (!flag)
For(i,n-1) printf("%d ",a[i]);printf("%d\n",a[n]);
sort(a+1,a+1+n*n);
h.clear();
For(i,n*n)
for(int x=1;x*x&=a[i];++x)
if (a[i]%x==0)
if (x*x&a[i]) ad(a[i]/x);
for(it=h.begin();it!=h.end();it++) {
int p=it-&first,s=it-&
h[p]=sqrt(h[p]);
it=h.end();it--;
int p=it-&first,s=it-&
ans[++siz]=p;
if (siz==n) break;
for(int x=1;x*x&=p;++x)
if (p%x==0)
if (x*x&p) h[p/x]--;
while (it-&second==0) it--;
For(i,siz-1) printf("%d ",ans[i]); printf("%d\n",ans[siz]);
没有更多推荐了，