【洛谷】NOIP提高组模拟赛Day1【组合数学】【贪心+背包】【网络流判断是否满流以及流量方案】
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 ;
}
最新文章
- Android 缓存
- 【转】MySQL中varchar最大长度是多少?
- P3398 仓鼠找sugar
- 第八篇:SOUI中控件事件的响应
- ArrayList和Vector的扩容机制
- python走起之第一话
- MySQL timestamp用法
- .NET下文本相似度算法余弦定理和SimHash浅析及应用
- python设计模式之装饰器模式
- linux系统关机与重新启动命令
- 正整数从1到N,输出按照字典序排序的前K个数
- BZOJ_2151_种树_贪心+堆+链表
- php OpenSSL 加解密
- [jPlayer]一分钟部署jPlayer
- 终止执行js的方法
- linux 命令大全,我去
- Ultra-QuickSort (POJ 2299)树状数组+离散化
- python中偏函数的应用
- 快捷键jdeveloper
- Spring Cloud(二):Spring Cloud Eureka Server高可用注册服务中心的配置