Codeforces 954E:Water Taps 贪心

zz/2024/5/21 21:40:54

传送门

题目描述

∀ x i ∈ [ 1 , a i ] , \forall x_i\in[1,a_i], xi[1,ai],对于所有满足 ∑ i = 1 n x i ( t i − T ) = 0 \sum_{i=1}^nx_i(t_i-T)=0 i=1nxi(tiT)=0的情况,求 ∑ i = 1 n x i \sum_{i=1}^nx_i i=1nxi的最大值

分析

我们可以计算大于m和小于m那一边更大,显然如果加和更小的那一边可以全部选取,只需要另一边来中和即可

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
int h[N],e[N],ne[N],idx;
int in[N];
vector<int> ans;
int n,m;
int a[N];
bool flag;void add(int x,int y){ne[idx] = h[x],e[idx] = y,h[x] = idx++;
}void dfs(int x){for(int i = h[x];~i;i = ne[i]){int j = e[i];dfs(j);if(a[j] != j && a[x] != a[j]){flag = false;}}if(a[x] == x) ans.push_back(x);
}int main(){flag = true;memset(h,-1,sizeof h);scanf("%d%d",&n,&m);while(m--){int x,y;scanf("%d%d",&x,&y);add(x,y);in[y]++;}for(int i = 1;i <= n;i++) scanf("%d",&a[i]);for(int i = 1;i <= n;i++)if(!in[i]){dfs(i);}if(!flag){puts("-1");return 0;}printf("%d\n",ans.size());for(auto t:ans) printf("%d\n",t);return 0;
}/**
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃       ┃
* ┃   ━   ┃ ++ + + +
*  ████━████+
*  ◥██◤ ◥██◤ +
* ┃   ┻   ┃
* ┃       ┃ + +
* ┗━┓   ┏━┛
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the animal protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃        ┣┓
*    ┃        ┏┛
*     ┗┓┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/

http://www.ngui.cc/zz/2727390.html

相关文章

CodeForces 792C :Divide by Three DP + 路径还原

传送门 题目描述 在一个黑板上写着一个正整数 n 。它有不超过10^5位&#xff08;话说黑板上是怎么写下这个数的&#xff09; 。老师给你了一个任务&#xff0c;把它魔改成一个 美丽数 &#xff0c;而且因为你很懒&#xff0c;你非常非常的想用最小的步数把它改成一个 美丽数 …

CodeForces 372C :Watching Fireworks is Fun DP + 单调队列

传送门 题目描述 给出N个位子&#xff0c;排成一列&#xff0c;现在有M个烟花&#xff0c;每秒人的速度d&#xff0c;每个烟花有三个元素&#xff1a;a&#xff0c;b&#xff0c;t&#xff0c;表示在时刻t会绽放&#xff0c;如果我们在位子x观看到了的话&#xff0c;会获得b-…

CodeForces 961D:Pair Of Lines 思维

传送门 题目描述 在平面直角坐标系上给出n个点&#xff0c;求是否存在两条直线穿过所有点。 分析 前面三个点中&#xff0c;任意两个点必成一条直线&#xff0c;所以我们去枚举三个点中的两个&#xff0c;然后去判断其他的点是否在这条直线上&#xff0c;然后再判断不在这条…

CodeForces 319B :Psychos in a Line 单调栈

传送门 题目描述 有编号为1~N的N个人站成一排&#xff08;顺序是乱的&#xff09;&#xff0c;每人手中拿着一把枪。每一个时刻&#xff0c;每个人同时瞄准右边的人&#xff08;如果存在的话&#xff09;&#xff0c;然后如果这个人编号比自己大&#xff0c;则开枪将他打死。…

Wireless Password :ac自动机 + 状压DP

分析 f[i][j][k]表示第i位的情况下&#xff0c;在trie图上的位置位j的情况下匹配情况位k&#xff0c;状态转移方程就比较好写了 dp[i 1][tr[j][c]][l | cnt[tr[j][c]]] (dp[i 1][tr[j][c]][l | cnt[tr[j][c]]] dp[i][j][l]) % mod注意一下减去不合法的状态&#xff0c;节…

CodeForces 1367E :Necklace Assembly 思维

传送门 题目描述 给你一个字符串&#xff0c;你从中挑选一些让它们成为一个环&#xff0c;使得这个环朝一个方向转 k k k下&#xff0c;与原来看起来一样&#xff0c;找到你能够满足这个条件的可以挑选的最多的字符数量。 分析 我们去枚举 k k k的因子&#xff0c;那么我转…

POJ - 3635 :Full Tank? 最短路 + 拆点

分析 跟前段时间看的一个拆点求邻接矩阵快速幂的一个题有点像 这个题比较朴素的方法就是我把每个点剩余 j j j单位的汽油的最低花费处理出来&#xff0c;然后这样写毫无疑问会tle&#xff0c;所以我们需要去进行一些优化 首先我们思考一下这个朴素的思想为什么会超时&#xff…

CodeForces 546E :Soldier and Traveling 网络流 +拆点

传送门 题目描述 题意大概就是给定 n n n 个城市&#xff0c; m m m 条边。 然后人只能从走相邻边相连的城市。 现在给你初始城市的每一个人数&#xff0c;再给一组每个城市人数。询问是否可以从当前人数变换到给定人数。如果能&#xff0c;输入“YES”并输出方案&#xff0…

CodeForces 1312E : Array Shrinking 区间DP

传送门 题目描述 给你一个序列 a i a_{i} ai​&#xff0c;相邻两个数如果相同的话&#xff0c;我们可以删去其中一个数字&#xff0c;另一个数字1&#xff0c;最后留下来的序列最小可以是多少 分析 这个数据范围大概就能想到是区间DP问题了 我们首先初始化每一个区间f[i][…

CodeForces 1447D :Catching Cheaters 字符串DP

传送门 题目描述 给我们两个字符串&#xff0c;让我们从中选出两个字串&#xff0c;算出它们的最大公共子序列长度。然后将它乘4在减去两个字串的长度。问你这个数最大是多少。 分析 我们可以把这个式子转换为2 * LIS - a的剩余长度 - b的剩余长度&#xff0c;然后就可以设…