Codeforces Round #592 (Div. 2)

A. Pens and Pencils

题目链接：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", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", 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;
}

View Code

B. Rooms and Staircases

题目链接：https://codeforces.com/contest/1244/problem/B

题意:

有一个两层的房子，每层有

#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", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", 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;
}

View Code

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", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", 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 << '\n';
                return 0;
            }
        }
    } 
    puts("-1");
    return 0;
}

View Code

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", (n))
#define pdd(n,m) printf("%d %d\n", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", 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;
}