A.水杯
一个模拟的水题..
Code:
int main()
{ll water_templat = -1,water_val = -1;ll L,A,B;read(n);read(L);read(A);read(B);for(int i=1;i<=n;i++){int opt,x;scanf("%d",&opt);if(opt!=3) scanf("%d",&x);if(opt == 1)water_templat = x;else if(opt == 2)water_val = x;else{if(water_templat>=A&&water_templat<=B&&water_val>=L) printf("%lld\n",water_templat);else printf("GG\n");}}return 0;
}
B.鳖
这个B...卡的直接醉了
按照题意模拟即可
模拟建议使用双端队列deque(最好还是数组吧,deque必须全局才可以)
被deque全局卡了一个小时40分钟
第一个坑点是注意摸牌顺序（可能会wa）
第二个坑点是处理摸牌顺序 (可能会T）
第三个坑点是删牌标记即可不要暴力删除（可能会T）
Code:
/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e17;
const int Maxn=2e7+10;
const int maxn =1e6+10;
const int mod= 1e9+7;
const int Mod = 1e9+7;
///const double eps=1e-10;
inline bool read(ll &num)
{char in;bool IsN=false;in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
int a[maxn],b[maxn];
int avis[maxn],bvis[maxn];
deque<int>qa,qb;
int cmpa(int x,int y){return avis[x]<avis[y];
}
int cmpb(int x,int y){return bvis[x] < bvis[y];
}
int main()
{int cntA = 0,cntB = 0;int ra = 0,rb = 0;read(n);for(int i=1;i<=4*n-2;i++){ll x;read(x);if(i&1){///Aliceif(!avis[x]){avis[x] = i,cntA++;}else {avis[x] = 0,cntA--;}}else{if(!bvis[x]) {bvis[x] = i,cntB++;}else {bvis[x] = 0,cntB--;}}}for(int i=1;i<=n;i++){if(avis[i]) a[++ra] = i;if(bvis[i]) b[++rb] = i;}sort(a+1,a+1+ra,cmpa);sort(b+1,b+1+rb,cmpb);for(int i=1;i<=ra;i++) qa.push_back(a[i]);for(int i=1;i<=rb;i++) qb.push_back(b[i]);int cnt = 0;while(cntA&&cntB){cnt++;if(cnt&1){while(qa.size()&&!avis[qa.front()]) qa.pop_front();cntA--;avis[qa.front()] = 0;if(bvis[qa.front()]){cntB--;bvis[qa.front()] = 0;}else{cntB++;bvis[qa.front()] = 1;qb.push_back(qa.front());qa.pop_front();}}else{while(qb.size()&&!bvis[qb.front()]) qb.pop_front();cntB--;bvis[qb.front()] = 0;if(avis[qb.front()]){cntA--;avis[qb.front()] = 0;}else{cntA++;avis[qb.front()] = 1;qa.push_back(qb.front());qb.pop_front();}}}printf("%d\n",cnt);return 0;
}
/**
13 10
1 2~12 13
**/
C.顺序安排
考虑每个节点访问其儿子节点数，在访问第二个儿子时肯定要访问第一个儿子
所以说，第一个儿子的所有节点在第二个儿子节点之前
其实这就是哈夫曼树的原理了，由于k是一样的，所以遍历儿子节点时，每个儿子节点应该按照节点顺序从小到大排列
这样可以保证最大的贡献只利用了一次
Code:
int sz[maxn];
vector<int>v[maxn],g;
void dfs(int u){sz[u] = 1;int szt = v[u].size();for(int k=0;k<szt;k++){int e = v[u][k];dfs(e);sz[u] +=sz[e];}
}
int cmp(int a,int b){return sz[a] < sz[b];
}
int main()
{read(n);read(m);for(int i=2;i<=n;i++){int x;scanf("%d",&x);v[x].push_back(i);}dfs(1);ll ans = m;for(int i=1;i<=n;i++){g.clear();int szt = v[i].size();for(int k=0;k<szt;k++){int e = v[i][k];g.push_back(e);}sort(g.begin(),g.end(),cmp);ll temp = 1;szt = g.size();for(int k=0;k<szt;k++){int x = g[k];ans += temp*m;temp += sz[x];}}printf("%lld\n",ans);return 0;
}
总结：
这次被B卡了1个小时40分钟，以至于A和C都没时间优化，C本来想着后期用链式前向星之类+并查集优化一下的
以后队列这种太大还是数组模拟吧..
最后rk3唉。
最后...这是打过最假的一场