Codeforces Round #592 (Div. 2) A. Pens and Pencils B. Rooms and Staircases C. The Football Season D. Paint the Tree
题目链接：https://codeforces.com/contest/1244/problem/A
题意：
给定五个数 a , b , c , d , k
求一对 x , y 使得 cx >= a , dy >= b , 且 x + y <= k
若无法找到满足条件的 x , y ，则输出 - 1
分析：
判断 a 是否能除尽 c , 如果能 , 则 x 最小可以为 c / a , 否则 x 最小可以为 a / c + 1
再判断 b 是否能除尽 d , 如果能 , 则 y 最小可以为 d / b , 否则 y 最小可以为 b / d + 1
然后再判断 x + y <= k 是否成立即可
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d ", (n)) #define pdd(n,m) printf("%d %d ", n, m) #define pld(n) printf("%lld ", n) #define pldd(n,m) printf("%lld %lld ", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define numm ch - 48 #define MOD 1000000007 #define INF 0x3f3f3f3f #define pi 3.14159265358979323 #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;} bool isPrime(ll n) {ll i,t;if(n==2||n==3)return 1;if(n%6!=1&&n%6!=5)return 0;t=sqrt(n);for(i=5;i<=t;i+=6)if(n%i==0||n%(i+2)==0)return 0;return 1;} const int N = 2e5 + 10; int a , b, c , d ,k; int main() { ios; int t; cin >> t; int ans1 , ans2 ; while(t--) { cin >> a >> b >> c >> d >> k; if(a % c == 0) ans1 = a / c; else ans1 = a / c + 1; if(b % d == 0) ans2 = b / d; else ans2 = b / d + 1; if(ans1 + ans2 <= k) cout << ans1 << " " << ans2 << endl; else cout << -1 << endl; } return 0; }
B. Rooms and Staircases
题目链接：https://codeforces.com/contest/1244/problem/B
题意:
有一个两层的房子，每层有 n 间屋子，每层的相邻两个屋子可以到达。两层之间有一些屋子有楼梯相连。
现在你可以选择从任意一间屋子出发 , 问在不走已经走过的屋子的前提下 , 你最多能走过多少间屋子
分析：
要想走更多的屋子, 肯定要从某一层的第一列或者最后一列出发
所以我们只要找所有楼梯距离第一列和最后一列的最大距离 max , 然后答案就是 2 * max
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d ", (n)) #define pdd(n,m) printf("%d %d ", n, m) #define pld(n) printf("%lld ", n) #define pldd(n,m) printf("%lld %lld ", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define numm ch - 48 #define MOD 1000000007 #define INF 0x3f3f3f3f #define pi 3.14159265358979323 #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;} bool isPrime(ll n) {ll i,t;if(n==2||n==3)return 1;if(n%6!=1&&n%6!=5)return 0;t=sqrt(n);for(i=5;i<=t;i+=6)if(n%i==0||n%(i+2)==0)return 0;return 1;} const int N = 2e5 + 10; int main() { int t; cin >> t; while(t--) { int n; cin >> n; string s; cin >> s; int minn = INF , maxn = -1; int len = s.size(); rep(i , 0 , len - 1) { if(s[i] == '1') { if(minn > i ) minn = i; if(maxn < i + 1) maxn = i + 1; } } if(minn == INF) { cout << n << endl; continue; } int ans = max(maxn , n - minn); cout << ans * 2 << endl; } return 0; }
C. The Football Season
题目链接：https://codeforces.com/contest/1244/problem/C
题意：
踢足球。 已知你进行了 N 场比赛 , 你的总得分为 P , 赢一场比赛加 w 分 , 平局加 d 分 , 输了不掉分（w > d）
现在你忘了你赢了多少场 , 平局了多少场 , 输了多少场 , 于是你要求出任意一组 x （胜场）, y （平场）, z（输场）
使得 x * w + y * d = N , x + y + z = P;
分析：
直接暴力枚举平局的场次就可以了 ，平局的场次最多为 lcm(w , d) / d - 1
因为当平局场次达到 lcm(w , d) / d 的时候 , 平局带来的分数为 lcm(w , d) / d * d , 而它等于 lcm(w , d) / w * w
即它可以转换成胜利了 lcm(w , d) / w 场 , 所以我们只要在枚举平局场次y的同时判断是否有满足条件的x即可
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d ", (n)) #define pdd(n,m) printf("%d %d ", n, m) #define pld(n) printf("%lld ", n) #define pldd(n,m) printf("%lld %lld ", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define numm ch - 48 #define MOD 1000000007 #define pi 3.14159265358979323 #define lrt rt<<1 #define rrt rt<<1|1 #define lson l, m, lrt #define rson m+1, r, rrt #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; const ll INF (0x3f3f3f3f3f3f3f3fll); template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;} ll mult_mod(ll a, ll b, ll c) {a%=c;b%=c;ll ret=0,tmp=a;while(b){if(b&1){ret+=tmp;if(ret>c)ret-=c;}tmp<<=1;if(tmp>c)tmp-=c;b>>=1;}return ret;} bool check(ll a, ll n, ll x, ll t) {ll v=pow_mod(a,x,n);ll s=v;rep(i,1,t){v=mult_mod(v,v,n);if(v==1&&s!=1&&s!=n-1)return true;s=v;} if(v!=1)return true;else return false;} bool Miller_Rabin(ll n) {if(n<2)return false;if(n==2)return true;if((n&1)==0)return false;ll x=n-1,t=0;while((x&1)==0){x>>=1;t++;}srand(time(NULL)); rep(i,0,19){ll a=rand()%(n-1)+1;if(check(a,n,x,t))return false;}return true;} const int N = 2e5 + 10; int main() { ios; ll n , p , w , d; cin >> n >> p >> w >> d; ll tot = lcm(w , d); tot /= d; tot -= 1; for(int i = 0 ; i <= tot && i <= n ; i ++) { ll win; ll he = p - d * i; if(he % w == 0 && he >= 0) { win = he / w; if(win + i <= n) { cout << win << " " << i << " " << n - win - i << ' '; return 0; } } } puts("-1"); return 0; }
D. Paint the Tree
题目链接：https://codeforces.com/contest/1244/problem/D
题意：
给定三种不同颜色的染料和一颗有 n 个节点的树 , 然后让你给树上色
要求每三个相邻节点的颜色不同 , 每个节点染上不同的颜色都有相应的费用 , 求最小花费
分析：
不难发现只有当这颗树为一条链的时候才能合法染色 , 且前两个节点的颜色确定了后剩下节点的颜色也就都确定了
所以我们只要枚举前两个节点的颜色 , 然后计算所有花费中的最小花费即可
#include<bits/stdc++.h> #define ios std::ios::sync_with_stdio(false) , std::cin.tie(0) , std::cout.tie(0) #define sd(n) scanf("%d",&n) #define sdd(n,m) scanf("%d%d",&n,&m) #define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k) #define pd(n) printf("%d ", (n)) #define pdd(n,m) printf("%d %d ", n, m) #define pld(n) printf("%lld ", n) #define pldd(n,m) printf("%lld %lld ", n, m) #define sld(n) scanf("%lld",&n) #define sldd(n,m) scanf("%lld%lld",&n,&m) #define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k) #define sf(n) scanf("%lf",&n) #define sff(n,m) scanf("%lf%lf",&n,&m) #define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,n,a) for (int i=n;i>=a;i--) #define mm(a,n) memset(a, n, sizeof(a)) #define pb push_back #define all(x) (x).begin(),(x).end() #define fi first #define se second #define ll long long #define numm ch - 48 #define MOD 1000000007 #define pi 3.14159265358979323 #define debug(x) cout << #x << ": " << x << endl #define debug2(x, y) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl; #define debug3(x, y, z) cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl; #define debug4(a, b, c, d) cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl; using namespace std; const ll INF (0x3f3f3f3f3f3f3f3fll); template<typename T>void read(T &res){bool flag=false;char ch;while(!isdigit(ch=getchar()))(ch=='-')&&(flag=true); for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);flag&&(res=-res);} template<typename T>void Out(T x){if(x<0)putchar('-'),x=-x;if(x>9)Out(x/10);putchar(x%10+'0');} ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a*b/gcd(a,b);} ll pow_mod(ll x,ll n,ll mod){ll res=1;while(n){if(n&1)res=res*x%mod;x=x*x%mod;n>>=1;}return res;} ll fact_pow(ll n,ll p){ll res=0;while(n){n/=p;res+=n;}return res;} bool isPrime(ll n) {ll i,t;if(n==2||n==3)return 1;if(n%6!=1&&n%6!=5)return 0;t=sqrt(n);for(i=5;i<=t;i+=6)if(n%i==0||n%(i+2)==0)return 0;return 1;} const ll N = 1e5 + 10; pair<ll , ll>haha; vector<ll>v[N] ; vector<pair<ll , ll>>v1[N]; ll ans , ans1 = INF; ll col[5][N] , n , luxie[N]; bool vis[N]; bool cmp(pair<ll ,ll>a , pair<ll ,ll> b) { return a.first < b.first; } int main() { cin >> n; rep(i , 0 , 2) rep(j , 1 , n) cin >> col[i][j]; rep(i , 1 , n - 1) { ll x , y; cin >> x >> y; v[x].pb(y) , v[y].pb(x); } rep(i , 1 , n) if(v[i].size() > 2) { cout << -1 << endl; return 0; } ll tot = 1 , num; rep(i , 0 , 2) { mm(vis , 0); ll flag = 0 , last , k = i , ans = 0 , num1 = 0 ; rep(j , 1 , n) { if(v[j].size() == 1) { haha.first = j , haha.second = k; v1[tot].pb(haha); ans += col[k % 3][j]; vis[j] = 1; flag = 1; k ++ , num1 ++; last = v[j][0]; break; } } while(num1 < n) { haha.first = last , haha.second = k % 3; v1[tot].pb(haha); ans += col[k % 3][last] , vis[last] = 1; rep(h , 0 , v[last].size() - 1) if(!vis[v[last][h]]){last = v[last][h] ; break ;} k++ , num1 ++; } if(ans1 > ans) ans1 = ans , num = tot; tot ++; } rep(i , 0 , 2) { mm(vis , 0); ll flag = 0 , last , k = i , ans = 0 , num1 = 0; rep(j , 1 , n) { if(v[j].size() == 1) { haha.first = j , haha.second = k; num1 ++; ans += col[k % 3][j]; v1[tot].pb(haha); k += 2; vis[j] = 1; flag = 1; last = v[j][0]; break; } } while(num1 < n) { haha.first = last , haha.second = k % 3; ans += col[k % 3][last] , vis[last] = 1; v1[tot].pb(haha); rep(h , 0 , v[last].size() - 1) if(!vis[v[last][h]]){last = v[last][h] ; break ;} k += 2; num1 ++; } if(ans1 > ans) ans1 = ans , num = tot; tot ++; } cout << ans1 << endl; sort(v1[num].begin() , v1[num].end() , cmp); rep(i , 0 , v1[num].size() - 2) cout << v1[num][i].second + 1<< " "; cout << v1[num][v1[num].size() - 1].second + 1 << endl; return 0; }