每日精选Codeforces训练题：1119E（贪心算法）、821C（栈模拟）和645D（拓扑排序）

有n种长度的棍子&＃xff0c;长度分别为2^0 ,2 ^ 1,…,2 ^ (n-1) ,每种棍子有a[i] 种&＃xff0c;问你能组成多少个三角形。
三角形两边之和大于第三边&＃xff0c;而2 ^ i &＃43; 2 ^ i &＃61; 2 ^ (i&＃43;1),所以两条短的边不能和一条长的边组成三角形&＃xff0c;因此要尽量组成2条长边1条短边的情况。
一开始是从后往前处理&＃xff0c;但是会出现问题&＃xff1a;当前剩2个的情况下到底是让比它小的的匹配&＃xff0c;还是让其和比它大的匹配。如1&＃xff0c;2&＃xff0c;2&＃xff0c;2&＃xff0c;2,当判断到第4个时可以选择让第四个的一个 和第五个的两个构成一个三角形&＃xff0c;也可以构成2个却一条边的三角形。并且无法判断哪一种选择更优。
所以这种贪心策略时有问题的。
而若从前往后进行选择&＃xff0c;首先当前最优的肯定是先把前面剩下的用2个给匹配掉&＃xff0c;然后是自己构成3个的&＃xff0c;然后剩下的1个或0个留给后面的解决

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mid ((l &＃43; r) >> 1)
#define Lson rt <<1, l , mid
#define Rson rt <<1|1, mid &＃43; 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define _for(i,a,b) for( int i &＃61; (a); i <(b); &＃43;&＃43;i)
#define _rep(i,a,b) for( int i &＃61; (a); i <&＃61; (b); &＃43;&＃43;i)
#define for_(i,a,b) for( int i &＃61; (a); i >&＃61; (b); -- i)
#define rep_(i,a,b) for( int i &＃61; (a); i > (b); -- i)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define hash Hash
#define next Next
#define f first
#define s second
using namespace std;
const int N &＃61; 3e5 &＃43; 10;
const double eps &＃61; 1e-9;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
int n, len;
LL a[N];
inline LL read(){LL s&＃61;0,w&＃61;1;char ch&＃61;getchar();while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)w&＃61;-1;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;) s&＃61;s*10&＃43;ch-&＃39;0&＃39;,ch&＃61;getchar();return s*w;
}
LL last, ans;
int main()
{IOS;n &＃61; read();_for(i,0,n){LL a;a &＃61; read();if(a / 2 >&＃61; last) {ans &＃43;&＃61; last; a -&＃61; last * 2; last &＃61; 0;}else ans &＃43;&＃61; a / 2, last -&＃61; a / 2, a %&＃61; 2;ans &＃43;&＃61; a / 3;a %&＃61; 3;last &＃43;&＃61; a;}cout << ans << endl;return 0;
}


C. Okabe and Boxes
简单的栈模拟
就是给你一个栈每次都加入一个数或者移除栈顶的元素移除的数的顺序必须按照1~n的顺序出栈&＃xff0c;如果不满足你可以重排栈顶元素&＃xff0c;问你最小需要重排的次数
我们可以假想成两个栈。如果不满足我们就将栈内的数重排放到假想的栈中&＃xff0c;并把实际的栈清空&＃xff08;细节要处理好就是每次remove的时候last &＃43;&＃43;

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mid ((l &＃43; r) >> 1)
#define Lson rt <<1, l , mid
#define Rson rt <<1|1, mid &＃43; 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define _for(i,a,b) for( int i &＃61; (a); i <(b); &＃43;&＃43;i)
#define _rep(i,a,b) for( int i &＃61; (a); i <&＃61; (b); &＃43;&＃43;i)
#define for_(i,a,b) for( int i &＃61; (a); i >&＃61; (b); -- i)
#define rep_(i,a,b) for( int i &＃61; (a); i > (b); -- i)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define hash Hash
#define next Next
#define f first
#define s second
using namespace std;
const int N &＃61; 3e5 &＃43; 10;
const double eps &＃61; 1e-9;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
int n, len;
LL str[N], top;
inline LL read(){LL s&＃61;0,w&＃61;1;char ch&＃61;getchar();while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)w&＃61;-1;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;) s&＃61;s*10&＃43;ch-&＃39;0&＃39;,ch&＃61;getchar();return s*w;
}
LL last &＃61; 1, ans;
int main()
{IOS;cin >> n;_for(i,0,2*n){char op[10];cin >> op;if(*op &＃61;&＃61; &＃39;r&＃39; && top &＃61;&＃61; 0){last &＃43;&＃43;;continue;}if(*op &＃61;&＃61; &＃39;r&＃39;){if(str[top - 1] &＃61;&＃61; last){last &＃43;&＃43;;top --;}else ans &＃43;&＃43;, top &＃61; 0, last &＃43;&＃43;;}else cin >> str[top], top &＃43;&＃43;;}cout << ans << endl;return 0;
}


题意&＃xff1a;
给你n个机器人和m组比较&＃xff0c;每组有a&＃xff0c;b&＃xff0c;表示a的能力比b强&＃xff0c;问你最少通过前多少组可以确定一个唯一的拓扑排序&＃xff0c;如果无法找到满足的结果输出-1
这个我们就要理解拓扑序列的算法本质了
拓扑序列是每次从入度为0的点开始跑&＃xff0c;并把与其相连的边删掉并且将下一组入度为0的点入队
那么其实我们发现我们删了一条边之后如果这条边相连的下一个点的入度为0了那么这条边就算是有贡献的&＃xff0c;那么我们就用map存一下每条边的编号&＃xff0c;统计一下有贡献的边最大位置在哪&＃xff0c;输出结果就好
如果途中有两个点同时度数为0这说明无法确定排名

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define mid ((l &＃43; r) >> 1)
#define Lson rt <<1, l , mid
#define Rson rt <<1|1, mid &＃43; 1, r
#define ms(a,al) memset(a,al,sizeof(a))
#define _for(i,a,b) for( int i &＃61; (a); i <(b); &＃43;&＃43;i)
#define _rep(i,a,b) for( int i &＃61; (a); i <&＃61; (b); &＃43;&＃43;i)
#define for_(i,a,b) for( int i &＃61; (a); i >&＃61; (b); -- i)
#define rep_(i,a,b) for( int i &＃61; (a); i > (b); -- i)
#define lowbit(x) ((-x) & x)
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define INF 0x3f3f3f3f
#define hash Hash
#define next Next
#define f first
#define s second
using namespace std;
const int N &＃61; 3e5 &＃43; 10;
const double eps &＃61; 1e-9;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
int n, m;
inline LL read(){LL s&＃61;0,w&＃61;1;char ch&＃61;getchar();while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)w&＃61;-1;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;) s&＃61;s*10&＃43;ch-&＃39;0&＃39;,ch&＃61;getchar();return s*w;
}
struct node {int to, next;
}e[N];
int head[N], cnt;
int d[N];
map<PII,int> mp;
inline void add(int from, int to)
{e[cnt] &＃61; {to,head[from]};head[from] &＃61; cnt &＃43;&＃43;;
}int tuopusort()
{queue<int> q;_for(i,1,n&＃43;1)if(d[i] &＃61;&＃61; 0)q.push(i);int maxv &＃61; -1;while(!q.empty()){if(q.size() >&＃61; 2) return -1;int u &＃61; q.front();q.pop();for(int i &＃61; head[u]; ~i; i &＃61; e[i].next){int v &＃61; e[i].to;d[v] --;if(!d[v]) q.push(v), maxv &＃61; max(mp[{u,v}],maxv);}}return maxv;
}int main()
{IOS;ms(head,-1);cin >> n >> m;_for(i,0,m){int l, r;cin >> l >> r;add(l,r);mp[{l,r}] &＃61; i &＃43; 1;d[r] &＃43;&＃43;;}cout << tuopusort();return 0;
}