U41568 Agent1
题目背景
2018年11月17日，中国香港将会迎来一场XM大战，是世界各地的ENLIGHTENED与RESISTANCE开战的地点，某地 的ENLIGHTENED总部也想派Agent去参加这次的XM大战，与世界其他地方的ENLIGHTENED并肩作战。
题目描述
某地的ENLIGHTENED总部总部有N个Agent，每个Agent的能力值互不相同，现在ENLIGHTENED行动指挥想要派出A,B两队Agent去参加XM大战。但是参加大战的两个队伍要满足两个要求：
- A队中能力最大的
Agent的能力值要小于B队能力最弱的Agent的能力值。 - A,B两队都要有人参战。
并不一定所有的Agent都要去参加XM大战的，心急的ENLIGHTENED行动指挥想知道有多少种安排Agent参加大战的方案。由于答案可能很大，所以只需要你求出答案模(109+7)的值就可以了。
输入输出格式
输入格式：
输入仅一行，为一个整数N。
输出格式：
输出答案模(109+7)的值。
输入输出样例
说明
对于20%的数据 N≤10
对于40%的数据 N≤103
对于60%的数据 N≤105
对于100%的数据 N≤109
背景影藏面目下的组合数学QAQ
也许我能推出来式子的组合式子就只能是$D1T1$水平了八QAQ
一开始找规律，发现要满足题目所给的条件，其实是分别在$n$个中找$2，3，4，5...n$个人的组合数方案在乘上$i-1$加起来。因为相当于要使小的连续一段在$A$，大的连续一段在$B$。
比如一共有5个人参赛，他们能力值就是$1、2、3、4、5$只能如下安排：
| A | B |
| 1 | 2 3 4 5 |
| 1 2 | 3 4 5 |
| 1 2 3 | 4 5 |
| 1 2 3 4 | 5 |
只有（5-1）= 4种方法，再乘上$n$中选$5$个人的组合数。
得到公式：$ans=\sum_{i=2}^n{{C_n^i}*(i-1)}$，60分到手。
但是答案显然要$O(1)$得到（$log$）。
发现每个单项式乘的$(i-1)$非常不美QAQ（$zyl$dalao原话%%），所以把整个式子先加上一整个$\sum_{i=2}^n{C_n^i}$，$ans = \sum_{i=2}^n{C_n^i}-(2^n-1-n)$。
然后依然是$zyl$dalao以前传授的！
$i\sum_n^i = n\sum_{n-1}^{i-1}$，在n个人中选i个人组成一队，再在其中选择1个人作为队长的方案数等于现在n个人中选1个人当队长，再在剩下n-1个人中选i-1个人做组员的方案数。是唯一记得最清楚的组合方程了QAQ
所以$ans = n\sum_{i=2}^n{C_{n-1}^{i-1}}-(2^n-1-n)$，所以$ans=n(2^{n-1}-1)-(2^n-1-n)$。
结果交上去还wa了一次！QAQ取模啊取模姐姐！！
#include<bits/stdc++.h>
#define mod 1000000007
#define LL long long
using namespace std; LL n; LL mpow(LL a, LL b) {
LL ans = ;
for(; b; b >>= , a = a * a % mod)
if(b & ) ans = ans * a % mod;
return ans;
} int main() {
scanf("%lld", &n);
LL ans = ((n * mpow(, n - ) % mod - (mpow(, n) - )) % mod + mod) % mod;
printf("%lld", ans);
return ;
}
U41569 Portal1
题目背景
Agent获取资源有很多种方式，HACK就是其中的一中，侵入Portal可以获得很多有用的资源。ENLIGHTENED总部因为参加XM大战，只剩下一点点可用资源了，所以ENLIGHTENED行动指挥想要进行HACK活动，尽量增加库存。
题目描述
地图上有N个可以被HACK的Portal，编号为1~N。HACK第ii号Portal需要时间T[i]秒，可以HACK出C[i]库存的资源。可是只有有能量的Portal才可以HACK出资源。第ii号Portal在第D[i]秒时，能量就会消失殆尽。ENLIGHTEDED想知道，最多可以增加多少库存，并且按编号小到大输出需要HACK的Portal的编号。
输入输出格式
输入格式：
第一行输入一个整数N
下接N行每行3个整数，T[i],D[i],C[i]
输出格式：
输出第一行为一个整数，最多可以增加多少库存。
第二行为一个整数，代表需要HACK多少个Portal。
第三行按编号小到大输出需要HACK的Portal的编号，若有多种HACK的方案输出其中一种即可。
输入输出样例
说明
对于20%的数据N≤5,T[i],C[i]≤5,D[i]≤10
对于40%的数据N≤20,T[i],C[i]≤10,D[i]≤100
对于60%的数据N≤50,T[i],C[i]≤15,D[i]≤1000
对于100%的数据 N≤100,T[i],C[i]≤20,D[i]≤2000
哭哭，本来以为自己从后往前DP完全正确的！结果后面状态还没更新，前面就更新了，爆错。
正确是先背包预处理出到达每天能获得最大的值，同时顺便处理出每个物品在当前时间点可不可以取。
因为背包的时候是正着枚举物品，虽然可能会覆盖，但是最后倒着取物品，就可以保证最后得到的物品是最优了。
#include<bits/stdc++.h>
using namespace std; int n; struct Node {
int t, c, d, id;
} hack[];
bool cmp(Node a, Node b) { return a.d < b.d; } int dp[], vis[][], QAQ[];
int main() {
scanf("%d", &n);
for(int i = ; i <= n; i ++)
scanf("%d%d%d", &hack[i].t, &hack[i].d, &hack[i].c), hack[i].id = i;
sort(hack + , hack + + n, cmp);
for(int i = ; i <= n; i ++)
for(int j = hack[i].d-; j >= hack[i].t; j --) {
if(dp[j] < dp[j-hack[i].t] + hack[i].c) {
dp[j] = dp[j-hack[i].t] + hack[i].c;
vis[i][j] = ;
}
}
int ans = ;
for(int i = ; i <= hack[n].d; i ++) if(dp[ans] < dp[i]) ans = i;
printf("%d\n", dp[ans]);
for(int i = n; i >= ; i --)
if(vis[i][ans]) QAQ[++QAQ[]] = hack[i].id, ans -= hack[i].t;
printf("%d\n", QAQ[]);
for(int i = QAQ[]; i >= ; i --)
printf("%d ", QAQ[i]);
return ;
}
U41570 War1
题目背景
XM大战来临之际，ENLIGHTENED总部为了抵御RESISTANCE的进攻，调整了某地Portal的能量值，使得其可以经受更多的打击。
题目描述
ENLIGHTENED总部有N个Portal，编号为1~N，编号为ii的Portal初始能量值为A[i]，在Portal之间有M条LINK，每条LINK着连接着两个不同Portal，被连接着的两个Portal可以相互传输能量，每个Portal最多总共只能向其连接着的Portal传输A[i]点能量，现在ENLIGHTENED行动指挥想让每第i个Portal的能量值变为B[i]，但他不知道着可不可行，所以找到了你，如果可行的话，需要你求出一种可行的能量传输方案。
能量只能之间传输不能间接传输
输入输出格式
输入格式：
第一行数两个个整数N,M。
第二行有N个整数，第i个整数代表A[i]
第三行有N个整数，第i个整数代表B[i]
下接M行，每行输入两个整数X,Y，代表编号为X的Portal到编号为Y的Portal有一条LINK。
输出格式：
若有可行方案输出YES，并且下接N行，每行N个整数，第i行第j个数代表代表编号为i的Portal向编号为j的Portal传输的能量值。若i=j输出第i个Portal传输后留下的能量值。若有多种可行方案输出其中一种即可。
若无可行方案输出NO
输入输出样例
说明
对于20%的数据 N≤10
对于40%的数据 N≤25
对于60%的数据 N≤50
对于100%的数据 N≤100,M≤2*N,0≤A[i],B[i]≤100
数据范围以及题目条件暗示网络流。
将每个点拆点，分别向起点和终点连边，流量分别为$A[i]$和$B[i]$，中间首先自己向自己连流量为无穷的边，相连的两个点连边，因为是互相，所以有两条。直接跑最大流，判断流量是否和$B[i]$的和相等即是流满，在把中间反边的流量取出来即是两点间运输方案。
一开始一直T，发现是$Bfs$里面判断是用的$dep$，而起点的$dep$没有赋值，导致可能死循环。所以以后还是要习惯用$vis$判断！！
#include<bits/stdc++.h>
#define oo 0x3f3f3f3f
using namespace std; void read(int &x) {
x = ; char ch = getchar();
while(ch > '' || ch < '') ch = getchar();
while(ch >= '' && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
} struct Node {
int u, v, nex, f, rev;
Node(int u = , int v = , int nex = , int f = , int rev = ) :
u(u), v(v), nex(nex), f(f), rev(rev) { }
} Edge[]; int h[], stot = ;
void add(int u, int v, int f) {
++stot;
Edge[stot] = Node(u, v, h[u], f, stot + );
h[u] = stot;
++stot;
Edge[stot] = Node(v, u, h[v], , stot - );
h[v] = stot;
} int n, m, s, t; int vis[], dep[];
queue < int > q;
bool bfs() {
memset(vis, , sizeof(vis));
memset(dep, , sizeof(dep));
q.push(s); vis[s] = ; dep[s] = ;
while(!q.empty()) {
int x = q.front(); q.pop();
for(int i = h[x]; i; i = Edge[i].nex) {
int v = Edge[i].v;
if(!dep[v] && Edge[i].f) {
dep[v] = dep[x] + ;
vis[v] = ;
q.push(v);
}
}
}
return vis[t];
} int dfs(int u, int delta) {
if(u == t || delta == ) return delta;
int res = ;
for(int i = h[u]; i && delta; i = Edge[i].nex) {
int v = Edge[i].v;
if(dep[v] == dep[u] + && Edge[i].f) {
int dd = dfs(v, min(delta, Edge[i].f));
Edge[i].f -= dd;
Edge[i^].f += dd;
res += dd;
delta -= dd;
}
}
return res;
} int sum;
int mp[][];
int main() {
scanf("%d%d", &n, &m);
int ans = ;
s = * n + , t = * n + ;
for(int i = ; i <= n; i ++) {
int a;
read(a);
add(s, i, a);
ans += a;
}
for(int i = ; i <= n; i ++) {
int b;
read(b);
add(i + n, t, b);
sum += b;
}
for(int i = ; i <= n; i ++) add(i, i + n, oo);
for(int i = ; i <= m; i ++) {
int a, b;
read(a); read(b);
add(a, b + n, oo);
add(b, a + n, oo);
}
if(ans != sum) {
printf("NO");
return ;
}
ans = ;
while(bfs()) ans += dfs(s, oo);
if(ans != sum) printf("NO");
else {
printf("YES\n");
for(int x = ; x <= n; x ++)
for(int i = h[x]; i; i = Edge[i].nex) {
int v = Edge[i].v;
if(v > n) mp[x][v-n] = Edge[Edge[i].rev].f;
}
for(int i = ; i <= n; i ++) {
for(int j = ; j < n; j ++) printf("%d ", mp[i][j]);
printf("%d\n", mp[i][n]);
}
}
return ;
}