题目链接 首先算出i在剩下比赛中全部获胜,看剩下的是否互相牵制,这样就转化成了公平分配问题的模型. #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1000 + 10; const int INF = 1000000000; struct Edge { int from, to, cap, flow; }; bool operator < (const Edge& a, const Edge& b) { return a.from < b.from || (a.from == b.from && a.to < b.to); } struct Dinic { int n, m, s, t; vector<Edge> edges; // 边数的两倍 vector<int> G[maxn]; // 邻接表,G[i][j 继续阅读 >>


楚东方 17/10/11 21:10:01
题目链接 问题分析 第一问时LIS,动态规划求解,第二问和第三问用网络最大流解决。 建模方法 首先动态规划求出F[i],表示以第i位为结尾的最长上升序列的长度,求出最长上升序列长度K。 1. 把序列每位i拆成两个点 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define MAXN 100010 #define MAXM 10000000+10 #define INF 0x3f3f3f3f struct Edge { int from, to, cap, flow, next; }; Edge edge[MAXM]; int head[MAXN], cur[MAXN], edgenum; int dist[MAXN]; bool vis[MAXN]; int N, M,ss,tt; void init() { edgenum = 0; memset(head, -1, sizeof(head)); } void 继续阅读 >>


楚东方 17/10/11 01:07:21
题目链接 要点,每个点之间可以连两条边,这样可以解决很多问题,该题中的数据被取出,则可以连一条有权重的边和若干条无权重的边. #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 10000; const int MAXM = 1000000; const int INF = 0x3f3f3f3f; struct Edge { int to,next,cap,flow,cost; } edge[MAXM]; int head[MAXN],tol; int pre[MAXN],dis[MAXN]; bool vis[MAXN]; int N;//节点总个数,节点编号从0~N-1 void init(int n) { N = n; tol = 0; 继续阅读 >>


楚东方 17/10/11 00:10:24
1650: [Usaco2006 Dec]River Hopscotch 跳石子 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 761  Solved: 479 [Submit][Status][Discuss] Description Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from the start (1 <= L <= 1,000,000 继续阅读 >>


楚东方 17/10/10 22:26:23
题目链接 建立二分图,跑一边最大流即可,最后再根据流量路径输出 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 41000; const int MAXM = 10000010; const int INF = 0x3f3f3f3f; //const ll MOD = 998244353; inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1; while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-') fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48, rx=getchar();return ra*fh;} struct Edge { int fro 继续阅读 >>


楚东方 17/10/10 11:08:42
题目链接 把棋盘黑白染色,构建二分图,然后s点连黑1 ,黑连白INF ,白连t 1,注意黑白相连为一步可达 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 41000; const int MAXM = 10000010; const int INF = 0x3f3f3f3f; //const ll MOD = 998244353; int dir[8][2]={ {2,1},{-2,1},{2,-1},{-2,-1} , {1,2},{1,-2},{-1,2},{-1,-2} }; inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1; while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-') fh=-1,rx=getchar();while(rx> 继续阅读 >>


楚东方 17/10/09 11:54:42
A. Bark to Unlock 注意特判相等的情况 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int INF = 1e9; inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1; while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-') fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48, rx=getchar();return ra*fh;} int n; string s; string w; int main() { // freopen("data.txt","r",stdin); ios_base::sync_with_stdio(false); ci 继续阅读 >>


楚东方 17/10/05 21:27:36
1651: [Usaco2006 Feb]Stall Reservations 专用牛棚 Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 1031  Solved: 582 [Submit][Status][Discuss] Description Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow c 继续阅读 >>


楚东方 17/10/05 18:06:27
图论 传递背包 用于判断任意两点是否存在关系 作者:chudongfang2015 发表于2017/9/26 20:59:55 原文链接 阅读:4 评论:0 查看评论 继续阅读 >>


楚东方 17/09/26 20:59:55
1600: [Usaco2008 Oct]建造栅栏 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 1348  Solved: 841 [Submit][Status][Discuss] Description 勤奋的Farmer John想要建造一个四面的栅栏来关住牛们。他有一块长为n(4<=n<=2500)的木板,他想把这块本板切成4块。这四块小木板可以是任何一个长度只要Farmer John能够把它们围成一个合理的四边形。他能够切出多少种不同的合理方案。注意: *只要大木板的切割点不同就当成是不同的方案(像全排列那样),不要担心另外的特殊情况,go ahead。 *栅栏的面积要大于0. *输出保证答案在longint范围内。 *整块木板都要用完。 Input *第一行:一个数n Output *第一行:合理的方案总数 Sample Input 6 Sample Output 6 输出详解: 继续阅读 >>


楚东方 17/09/25 23:14:38