题解"/>
HZNU Dec. Team Training 2题解
HZNU Dec. Team Training 2
A - Amateur Chess Players（Gym - 102606A）
题意：一个棋盘，Cuber QQ有n个棋和Quber CC有m个棋，没人可以拿同一条直线的棋子，每次至少拿一个，Cuber QQ先手，谁拿不了谁就输。
要想赢，每次只拿一个，就比较n,m。
代码：
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<fstream>
#include<iomanip>
#include<sstream>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x&-x)
#define debug cout<<"What fuck!!"<<endl
#define fcio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
int main(){int n,m;while(cin>>n){string s;for(int i=1;i<=n;++i)cin>>s;cin>>m;for(int i=1;i<=m;++i)cin>>s;if(n>m)cout<<"Cuber QQ"<<endl;else cout<<"Quber CC"<<endl;} return 0;
}B - Position in Fraction（CodeForces - 900B ）
题意：找到a/b小数点后第一次出现c的位置
代码：
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<fstream>
#include<iomanip>
#include<sstream>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x&-x)
#define debug cout<<"What fuck!!"<<endl
#define fcio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
map<int,int>mp;
int main(){int a,b,c;while(cin>>a>>b>>c){int now=0,cnt=0;a*=10;while(1){mp[a]++;if(a<b){cnt++;if(a==0)a=10;else a*=10;now=0;}else{now=a/b;a=a%b;cnt++;a*=10;}if(now==c){cout<<cnt<<endl;break;}if(mp[a]){cout<<-1<<endl;break;}}}return 0;
}C - LIKE vs CANDLE （HDU - 4799）
题意：若干微博账户形成了一个转发树（即一个有根树）。每个账户有自己的价值，每个账户也有自己的态度（赞或蜡烛）。如果一个账户的态度是“赞”，它的价值就会被加到“赞”的一边，反之亦然。Edward可以从“赞”的一边拿出X 的价值去翻转一个账户，即把它的态度换到相反的一边。但是Edward 发现，有的账户已经被别人翻转过了，对于这些账户，Edward就要花费Y的价值去翻转它们。一旦一个账户被翻转了一次，它的所有子账户也会被翻转一次。求“赞”的一边的价值总数与“蜡烛”一边的价值总数的最大差值。若最大差值为负数则输出“HAHAHAOMG”。
代码：
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<fstream>
#include<iomanip>
#include<sstream>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x&-x)
#define debug cout<<"What fuck!!"<<endl
#define fcio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=50010;
const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
int dp[maxn][2];
//dp[][0]---不翻转的最大值
//dp[][1]---翻转的最大值
int n,x,y;
int v[maxn],s[maxn];
//v---得分,正数支持like，负数支持candle
//s---标记是否翻转，0为没翻转，1为翻转
int f,p;
bool vis[maxn],flag;
vector<int>eg[maxn];
void init(){for(int i=0;i<=n;++i)eg[i].clear();memset(vis,false,sizeof vis);memset(dp,0,sizeof dp);flag=false;
}
void dfs(int u){vis[u]=true;if(s[u])flag^=1;if(flag)v[u]=-v[u];dp[u][0]=v[u];dp[u][1]-=v[u];for(int i=0;i<eg[u].size();++i){int to=eg[u][i];if(!vis[to]){dfs(to);if(s[to]){dp[u][0]=dp[u][0]+max(dp[to][0],dp[to][1]-y);dp[u][1]=dp[u][1]+max(dp[to][1],dp[to][0]-y);}else{dp[u][0]=dp[u][0]+max(dp[to][0],dp[to][1]-x);dp[u][1]=dp[u][1]+max(dp[to][1],dp[to][0]-x);}}}if(s[u])flag^=1;
}
int main(){fcio;while(cin>>n>>x>>y){init();for(int i=1;i<=n;++i){cin>>v[i]>>f>>s[i]>>p;if(p)v[i]=-v[i];eg[f].push_back(i);}dfs(0);if(dp[0][0]<0)cout<<"HAHAHAOMG"<<endl;else cout<<dp[0][0]<<endl;}return 0;
}D - Idiotic Suffix Array （Gym - 102606I）
题意：构造一个字符串，使本身在所有后缀字符串中从小到大排序为k,比较字符串时，第一个不相等的字符按字母表排序。并且当a是b的前缀是，a<b.
例如：a<aba
代码
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<fstream>
#include<iomanip>
#include<sstream>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x&-x)
#define debug cout<<"What fuck!!"<<endl
#define fcio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
int main(){fcio;int n,k;while(cin>>n>>k){for(int i=1;i<=n;++i){if(i==n-k+1)cout<<'b';else cout<<'a';}cout<<endl;}return 0;
}E - Find / -type f -or -type d （Gym - 102606F）
代码：
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<fstream>
#include<iomanip>
#include<sstream>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x&-x)
#define debug cout<<"What fuck!!"<<endl
#define fcio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=1e5+10;
const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
int n;
string s[maxn];
map<string,int>vis;
set<string>se;
int main(){while(cin>>n){for(int i=1;i<=n;++i)cin>>s[i];for(int i=1;i<=n;++i){string tmp;for(int j=0;j<s[i].length();){if(s[i][j]=='/'){tmp=tmp+'/';j++;while(j<s[i].length()&&s[i][j]!='/'){tmp=tmp+s[i][j];j++;}se.insert(tmp);//每个目录或文件名字 if(j<s[i].length())//将目录标记 vis[tmp]=1;}}}int cnt=0;for(auto it:se){if(!vis[it]){int len=it.length();if(it.length()>=5&&it[len-1]=='j'&&it[len-2]=='o'&&it[len-3]=='e'&&it[len-4]=='.')//符合条件 cnt++;}}cout<<cnt<<endl;}return 0;
}F - Even Degree （Gym - 102606E）
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<fstream>
#include<iomanip>
#include<sstream>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x&-x)
#define debug cout<<"What fuck!!"<<endl
#define fcio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=5e5+10;
const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
vector<pair<int,int> >vec[maxn];
pair<int,int>f[maxn];
bool vis[maxn],used[maxn];
int now[maxn],ans[maxn],cnt,res[maxn],tot;
int n,m;
void dfs(int u){used[u]=1;while(now[u]<vec[u].size()){int v=vec[u][now[u]].first;int id=vec[u][now[u]].second;now[u]++;if(vis[id])continue;vis[id]=1;dfs(v);ans[++cnt]=id;}
}
int ano(int x,int id){return f[id].first^f[id].second^x;
}
int main(){fcio;while(cin>>n>>m){for(int i=1;i<=m;++i){int u,v;cin>>u>>v;f[i]=make_pair(u,v);vec[u].push_back(make_pair(v,i));vec[v].push_back(make_pair(u,i));}for(int i=1;i<=n;++i){if(!vec[i].size())continue;if(!used[i]){cnt=0;dfs(i);int now=i;int nex=ano(i,ans[1]); res[++tot]=ans[1];for(int j=2;j<cnt;++j){if(ano(nex,ans[j])==now){res[++tot]=ans[j+1];res[++tot]=ans[j];nex=ano(now,ans[j+1]);j++;}else{res[++tot]=ans[j];nex=ano(nex,ans[j]);}}}}cout<<tot<<endl;for(int i=1;i<=tot;++i){cout<<res[i];if(i==tot)cout<<endl;else cout<<" ";}}return 0;
}G - Invitation Cards （POJ - 1511）
#include <iostream>
#include <cmath>
#include <string>
#include <queue>
#include <cstring>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <stack>
#define fcio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define eps 1e-12
#define MEM(a,b) memset(a,b,sizeof a)
using namespace std;
typedef long long ll;
const int maxn = 1000010;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll dis[2][maxn];
int n, m, x, len, px;
class node {
public:int n;ll v;node() {}node(int x, ll y) :n(x), v(y) {}bool operator<(const node& a)const {return v == a.v ? n > a.n : ( !px ? v<a.v : v > a.v);}
};
class edge {
public:int to;int next;ll cost;edge() {}edge(int x,int y, ll z) :to(x),next(y), cost(z) {}
};
edge G[maxn*2];
int head[2][maxn];
bool vis[maxn];
void dijkstra(int fx) {priority_queue<node> que;dis[fx][1] = 0;que.push(node(1, 0)); //把起点推入队列MEM(vis, 0);while (!que.empty()){node p = que.top(); que.pop();int v = p.n; //顶点的编号if (vis[v]) continue;//d[v]可能经过松弛后变小了，原压入堆中的路径失去价值vis[v] = 1;for (int i = head[fx][v];i;i = G[i].next) {//利用最短边进行松弛int to = G[i].to;ll w = dis[fx][v] + G[i].cost;if (dis[fx][to] > w) {dis[fx][to] = w;que.push(node(to, dis[fx][to]));}}}
}
void init() {MEM(dis, inf);len = 1;MEM(head,0);
}
void add(int fx, int u, int v, ll w) {G[len].cost = w;G[len].to = v;G[len].next = head[fx][u];head[fx][u] = len++;
}
int main()
{fcio;int t;scanf("%d", &t);while (t--) {scanf("%d%d", &n, &m);init();ll c;for (int i = 0, a, b; i < m; i++)scanf("%d%d%lld", &a, &b, &c), add(0, a, b, c), add(1, b, a, c);px = 0;dijkstra(0);px = 1;dijkstra(1);ll maxx = 0;for (int i = 1; i <= n; i++)maxx += dis[0][i] + dis[1][i];printf("%lld\n", maxx);}return 0;
}
H - Thanos’s snap （Gym - 102409I ）
代码：
#include<map>
#include<set>
#include<list>
#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<fstream>
#include<iomanip>
#include<sstream>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x&-x)
#define debug cout<<"What fuck!!"<<endl
#define fcio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=5e6+10;
const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
ll fac[maxn],inv[maxn],dp[maxn];
ll fun(int m,int n){if(n==m||m==0)return 1;return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
ll qpow(ll a, ll b) {ll res = 1;while (b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}
void init(){fac[0]=1;for(int i=1;i<=5000000;++i)fac[i]=(fac[i-1]*i)%mod;inv[5000000]=qpow(fac[5000000],mod-2);for(int i=4999999;i>=0;--i)inv[i]=(inv[i+1]*(i+1))%mod;dp[5000000]=195206359;dp[0]=1;for(int i=4999999;i>=0;--i)dp[i]=(dp[i+1]+fun(i,5000000)*195206359)%mod;
}
int main(){fcio;int T;init();while(cin>>T){while(T--){int n;cin>>n;cout<<dp[n]<<endl;}}return 0;
}I - Heat Pipes （Gym - 102606H）
题解博客：
更多推荐
HZNU Dec. Team Training 2题解
发布评论