Codeforces Round #615 (Div. 3)

2019/04/10 10:10
阅读数 11

A. Collecting Coins

题目链接:https://codeforces.com/contest/1294/problem/A

题意:

你有三个姐妹她们分别有 a , b , c枚硬币,你有n枚,你可以把硬币随意分给她们(必须分完),使她们的硬币数A = B = C 

分析:

题目的条件有两点:

①A = B = C

②在满足①的前提下必须把硬币分完

我们首先要满足第一点。因为硬币个数有限,我们要尽可能用最少的硬币使 A = B = C,所以只要让a,b,c中小的两个等于最大的即可

那么我们剩下的硬币数就为 $n-\left( \max -a\right) -\left( \max -b\right) -\left( \max -c\right)$ 判断剩余数是否大于0即可(是否足够分配)

对于第二个条件,只要判断我们剩下的硬币是否是三的倍数即可(只有为三倍数才可以等量均分保持A = B = C)

#include<bits/stdc++.h>
using namespace std; 
int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int a , b , c , n;
        cin >> a >> b >> c >> n;
        int MAX = max(a , max(b , c));
        n -= (MAX - a) + (MAX - b) + (MAX - c);
        if(n < 0 || n % 3 != 0)
        cout << "NO" << '\n';
        else 
        cout << "YES" << '\n';
    }
    return 0;
}
 
 
 
 
   
View Code

 

 

 

B. Collecting Packages

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

题意:

有n个盒子需要你捡,第i个盒子的坐标为 (Xi , Yi)。你从(0,0)出发,每次只能选择向上或者向右移动,问能否将n个盒子都捡完,若可以捡完,则输出字典序最小的一条路线

分析:

我们将n个盒子的坐标先按照x值再按照y值排序。因为是按照 X 升序排序的,所以当 Yi  > Yi + 1 时,很显然此时第i个盒子和第i+1个盒子有一个不能走到

而 Yi <= Yi+1 时,为了保证字典序最小,我们先加上(Xi+1 - Xi)个L, 再加上(Yi+1 - Yi)个纵坐标即可

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int N = 2e5 + 10;
pair<int , int> ha[N];
int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int n , flag = 1 ; string ans = "";
        cin >> n;
        for(int i = 1 ; i <= n ; i ++)
            cin >> ha[i].fi >> ha[i].se;
        ha[0].fi = 0 , ha[0].se = 0;
        sort(ha , ha + 1 + n);
        for(int i = 0 ; i < n ; i ++)
        {
            if(ha[i].se > ha[i + 1].se)
            {
                flag = 0 ; break;
            }
            int dis1 = ha[i + 1].fi - ha[i].fi;
            int dis2 = ha[i + 1].se - ha[i].se;
            while(dis1)
            ans += "R" , dis1 --;
            while(dis2)
            ans += 'U' , dis2 --;
        }
        if(flag)
        cout << "YES" << '\n' << ans << '\n';
        else 
        cout << "NO" << '\n';
    }
    return 0;
} 
View Code

 

 

 

C. Product of Three Numbers

题目链接:https://codeforces.com/contest/1294/problem/C

题意:

给你一个 n ,要求三个整数 a ,b ,c 使得 a * b * c = n 并且 a、b、c >= 2

分析:

先枚举 n 的因子,再枚举因子的因子即可

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int n;
        cin >> n;
        int ans1 , ans2 , ans3;
        int flag = 0;
        for(int i = 2 ; i * i <= n ; i ++)
        {
            if(n % i == 0)
            {
                for(int j = 2 ; j * j < i ; j ++)
                {
                    if(i % j) continue;
                    ans1 = n / i , ans2 = j , ans3 = i / j;
                    flag = 1 ;
                    break;
                }
                int now = n / i;
                for(int j = 2 ; j * j < now ; j ++)
                {
                    if(now % j || now / j == i || j == i) continue;
                    ans1 = i , ans2 = j , ans3 = now / j;
                    flag = 1 ;
                    break;
                }
            }
        }
        if(!flag) cout << "NO" << '\n';
        else cout << "YES" << '\n' << ans1 << " " << ans2 << " " << ans3 << '\n';
    }
    return 0;
}
View Code

 

 

 

D. MEX maximizing

题目链接:https://codeforces.com/contest/1294/problem/D

题意:

给你 q 个询问和 一个 x , 每次询问输入一个数 n ,你可以把它减任意次 x 或 加任意次 x,然后添入数组,问每次询问结束时数组里最小的没出现的非负整数是多少

分析:

我们可以想象有若干个长度为 x 的区间[0 , x - 1] ,那么每次询问的数 n 只会出现在某个区间的 n % x位置上。为了满足题目要求,我们要尽可能让它填在比较靠前的区间里

cnt [i] 表示此次询问时,若干个区间一共有cnt[i] 个 i 可以填到若干个区间中的 i 位置上(为了满足题目要求,我们从第一个区间的第i个位置开始填,然后再填第二个区间第i个位置)

然后我们从第一个区间开始检查。若到当前位置时cnt[i] != 0,则我们让cnt[i] --(表示我们拿一个i填在这个位置上),同时往下一个位置跳,直到遇到一个没有数可填的位置——cnt[pos] = 0

#include<bits/stdc++.h>
using namespace std;
map<int , int>cnt;
int main()
{
    int q , x , ans = 0;
    cin >> q >> x;
    while(q --)
    {
        int n;
        cin >> n;
        cnt[n % x] ++;
        while(cnt[ans % x])
        cnt[ans % x] -- , ans ++;
        cout << ans << '\n';
    }
    return 0;
}
View Code

 

 

 

E. Obtain a Permutation

题目链接:https://codeforces.com/contest/1294/problem/E

题意:

给你一个 n * m 的矩阵,你执行两种操作:

① 把矩阵中任意一个元素改为任意一个数

② 把矩阵中任意一列整体往上挪一个单元格,如下图矩阵我们对第一列向上挪了一个单元格

现要求用最少的操作次数使矩阵内每一个元素 a[i][j] = (i - 1) * m + j

分析:

因为题目只能对一列或者一个元素进行操作,所以我们逐列进行维护。

对第i行第j列的元素a[i][j] 我们假设它将成为这列的起点(第一个元素) 那么最坏的操作次数cost[i]为 i + N (把它移动到第1位需要i次 如果元素全都很奇葩需要更改N次) 

对于每一列的操作,我们先初始化cost[i] = i + N , 然后如果a[i][j]可以作为第h行的答案的答案,那么cost[h] --(把a[h][j]行设为起点的最坏操作- 1)

最后遍历cost[1] ~ cost[n] 挑选最小的cost加到ans里即可

#include<bits/stdc++.h>
using namespace std; 
const int N = 2e5 + 10;
int main()
{
    int n , m ;
    cin >> n >> m;
    vector<vector<int>>a(n , vector<int>(m));
    for(int i = 0 ; i < n ; i ++) for(int j = 0 ; j < m ; j ++)
    {
        cin >> a[i][j];
        a[i][j] --;
    }
    int ans = 0;
    for(int j = 0 ; j < m ; j ++)
    {
        vector<int>cost(n);
        for(int i = 0 ; i < n ; i ++) cost[i] = i + n;
        for(int i = 0 ; i < n ; i ++)
        {
            if(a[i][j] % m == j && a[i][j] < n * m)
            {
                int h = i - a[i][j] / m; 
                if(h < 0) h += n;
                cost[h] --; 
            }       
        }
        ans += *min_element(cost.begin() , cost.end()); 
    }
    cout << ans << '\n';
    return 0;
}
View Code

 

 

 

F. Three Paths on a Tree

题目链接:https://codeforces.com/contest/1294/problem/F

题意:

给你一棵树,要求你找出任意三点 A,B,C,使得 A~B,B~C,A~C 之间的边最多(边并集最大)

分析:

比赛最后几分钟做出来了,然而一时马虎,提交到E题上去了。然后评测机也不给力,等赛后几分钟我才知道交错题了。再放到F题上提交,一发就过了。。。

证明一组最优解中一定有两个点是直径的两端点,那么题目就转换成求树直径端点及与两端点边并集最大的点,于是就很简单了

我们先一次bfs求出树直径DIS即其一端点A,再对端点A进行bfs求出另一端点B及每个点到端点A的距离dis1[i],最后再bfs端点B求出每个点到B的距离dis2[i]

最后遍历每个点,取边并集最大的即可(边并集= $\dfrac {dis1\left[ i\right] +dis2\left[ i\right] -DIS}{2}+DIS$)

现在给出证明

假设某个答案取连接点x。x最远的树到达的点是s,根据树的直径算法,s是树的某个直径a的端点。假设x的最远和第二远的点组成的链是b,b就会和a有一段公共部分。我们取a和b相交部分距离s最远的那个点y。那么取这个链上点y的答案一定比x更优  

 

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
struct Edge{
    int nex , to , w;
}edge[N];
int one , two , DIS;
int head[N] , vis[N] , d[N];
int tot = 0;
void add(int u , int v , int w)
{
    edge[tot].w = w;
    edge[tot].to = v;
    edge[tot].nex = head[u];
    head[u] = tot ++; 
}
int bfs(int st)
{
    memset(d , 0 , sizeof(d));
    memset(vis , 0 , sizeof(vis));
    queue<int>que;
    que.push(st);
    vis[st] = 1;
    int now;
    while(!que.empty())
    {
        now = que.front() , que.pop();
        for(int i = head[now] ; ~i ; i = edge[i].nex)
        {
            int TO = edge[i].to;
            if(vis[TO]) continue;    
            d[TO] = d[now] + edge[i].w;
            vis[TO] = 1;
            que.push(TO);
            if(DIS < d[TO]) DIS = d[TO]; 
        }
    }
    return now;
}
int dis1[N] , dis2[N]; 
int main()
{
    ios::sync_with_stdio(false);
    memset(head , -1 , sizeof(head)); 
    int n ;
    cin >> n;
    for(int i = 1 ; i < n ; i ++)
    {
        int x , y;
        cin >> x >> y;
        add(x , y , 1);
        add(y , x , 1);
    }
    DIS = 0;
    int one , two , three;
    one = bfs(1);
    two = bfs(one);
    for(int i = 1 ; i <= n ; i ++)
    dis1[i] = d[i];
    bfs(two);
    for(int i = 1 ; i <= n ; i ++)
    dis2[i] = d[i];
    int ans = 0;
    for(int i = 1 ; i <= n ; i ++)
    {
        if((dis1[i] + dis2[i] - DIS) / 2 + DIS > ans && i != one && i != two)
        ans = (dis1[i] + dis2[i] - DIS) / 2 + DIS , three = i;
    }
    cout << ans << '\n';
    cout << one << " " << two << " " << three << '\n';
    return 0;
}    
View Code

 

  为了更好的供人观看,每一份代码我都是重新手写的,请多支持

原文出处:https://www.cnblogs.com/StarRoadTang/p/12230408.html

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部