Codeforces Round #494 (Div. 3)

题目链接:http://henuly.top/?p=558

A. Polycarp’s Pockets

题目:

Polycarp has n coins, the value of the i-th coin is ai. Polycarp wants to distribute all the coins between his pockets, but he cannot put two coins with the same value into the same pocket.
For example, if Polycarp has got six coins represented as an array a=[1,2,4,3,3,2], he can distribute the coins into two pockets as follows: [1,2,3],[2,3,4].
Polycarp wants to distribute all the coins with the minimum number of used pockets. Help him to do that.

Input:

The first line of the input contains one integer n (1n100) — the number of coins.
The second line of the input contains n integers a1,a2,,an (1ai100) — values of coins.

Output

Print only one integer — the minimum number of pockets Polycarp needs to distribute all the coins so no two coins with the same value are put into the same pocket.

Sample Input:

6
1 2 4 3 3 2

Sample Output:

2

Sample Input:

1
100

Sample Output:

1

题目链接

一个集合不能有重复的数字,问所给序列能构成多少种集合。

直接统计个数最多的数字就是结果。

AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    map<int, int> m;
    int n;
    read(n);
    int x;
    int ans = -INF;
    for (int i = 0; i < n; ++i) {
        read(x);
        m[x]++;
        if (m[x] > ans) {
            ans = m[x];
        }
    }
    printf("%d\n", ans);
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("gedit out.txt");
#endif
    return 0;
}

B. Binary String Constructing

题目:

You are given three integers a, b and x. Your task is to construct a binary string s of length n=a+b such that there are exactly a zeroes, exactly b ones and exactly x indices i (where 1i<n) such that sisi+1. It is guaranteed that the answer always exists.
For example, for the string “01010” there are four indices i such that 1i<n and sisi+1 (i=1,2,3,4). For the string “111001” there are two such indices i (i=3,5).
Recall that binary string is a non-empty sequence of characters where each character is either 0 or 1.

Input:

The first line of the input contains three integers a, b and x (1a,b100,1x<a+b).

Output

Print only one string s, where s is any binary string satisfying conditions described above. It is guaranteed that the answer always exists.

Sample Input:

2 2 1

Sample Output:

1100

Sample Input:

3 3 3

Sample Output:

101100

Sample Input:

5 3 6

Sample Output:

01010100

题目链接

一个字符串含有a个0,b个1,x处str[i]≠str[i+1],构造符合要求的字符串。

将x分奇数偶数讨论,先在字符串最前面用“10”或“01”尽可能填满x,最后补没用完的0和1。

AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int a, b, x;
    read(x); read(b); read(x);
    if (x % 2) {
        if (a > b) {
            for (int i = 0; i < x / 2; ++i) {
                cout << "01";
            }
            cout << string(a - x / 2, '0');
            cout << string(b - x / 2, '1');
        }
        else {
            for (int i = 0; i < x / 2; ++i) {
                cout << "10";
            }
            cout << string(b - x / 2, '1');
            cout << string(a - x / 2, '0');
        }
    }
    else {
        if (a > b) {
            for (int i = 0; i < x / 2; ++i) {
                cout << "01";
            }
            cout << string(b - x / 2, '1');
            cout << string(a - x / 2, '0');
        }
        else {
            for (int i = 0; i < x / 2; ++i) {
                cout << "10";
            }
            cout << string(a - x / 2, '0');
            cout << string(b - x / 2, '1');
        }
    }
    printf("\n");
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("gedit out.txt");
#endif
    return 0;
}

C. Intense Heat

题目:

The heat during the last few days has been really intense. Scientists from all over the Berland study how the temperatures and weather change, and they claim that this summer is abnormally hot. But any scientific claim sounds a lot more reasonable if there are some numbers involved, so they have decided to actually calculate some value which would represent how high the temperatures are.
Mathematicians of Berland State University came up with a special heat intensity value. This value is calculated as follows:
Suppose we want to analyze the segment of n consecutive days. We have measured the temperatures during these n days; the temperature during i-th day equals ai.
We denote the average temperature of a segment of some consecutive days as the arithmetic mean of the temperature measures during this segment of days. So, if we want to analyze the average temperature from day x to day y, we calculate it as i=xyaiyx+1 (note that division is performed without any rounding). The heat intensity value is the maximum of average temperatures over all segments of not less than k consecutive days. For example, if analyzing the measures [3,4,1,2] and k=3, we are interested in segments [3,4,1], [4,1,2] and [3,4,1,2] (we want to find the maximum value of average temperature over these segments).
You have been hired by Berland State University to write a program that would compute the heat intensity value of a given period of days. Are you up to this task?

Input:

The first line contains two integers n and k (1kn5000) — the number of days in the given period, and the minimum number of days in a segment we consider when calculating heat intensity value, respectively.
The second line contains n integers a1, a2, …, an (1ai5000) — the temperature measures during given n days.

Output

Print one real number — the heat intensity value, i. e., the maximum of average temperatures over all segments of not less than k consecutive days.
Your answer will be considered correct if the following condition holds: |resres0|<106, where res is your answer, and res0 is the answer given by the jury’s solution.

Sample Input:

4 3
3 4 1 2

Sample Output:

2.666666666666667

题目链接

求序列长度不小于k的子区间中的最大平均值。

暴力。

AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n, k;
    read(n); read(k);
    vector<int> sum(n + 1);
    sum[0] = 0;
    int x;
    for (int i = 1; i <= n; ++i) {
        read(x);
        sum[i] = sum[i - 1] + x;
    }
    double ans = -INF;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + k - 1; j <= n; ++j) {
            double temp = (double)(sum[j] - sum[i -1]) / (double)(j - i + 1);
            ans = temp > ans ? temp : ans;
        }
    }
    printf("%.15lf\n", ans);
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("gedit out.txt");
#endif
    return 0;
}

D. Coins and Queries

题目:

Polycarp has n coins, the value of the i-th coin is ai. It is guaranteed that all the values are integer powers of 2 (i.e. ai=2d for some non-negative integer number d).
Polycarp wants to know answers on q queries. The j-th query is described as integer number bj. The answer to the query is the minimum number of coins that is necessary to obtain the value bj using some subset of coins (Polycarp can use only coins he has). If Polycarp can’t obtain the value bj, the answer to the j-th query is -1.
The queries are independent (the answer on the query doesn’t affect Polycarp’s coins).

Input:

The first line of the input contains two integers n and q (1n,q2105) — the number of coins and the number of queries.
The second line of the input contains n integers a1,a2,,an — values of coins (1ai2109). It is guaranteed that all ai are integer powers of 2 (i.e. ai=2d for some non-negative integer number d).
The next q lines contain one integer each. The j-th line contains one integer bj — the value of the j-th query (1bj109).

Output

Print q integers ansj. The j-th integer must be equal to the answer on the j-th query. If Polycarp can’t obtain the value bj the answer to the j-th query is -1.

Sample Input:

5 4
2 4 8 2 4
8
5
14
10

Sample Output:

1
-1
3
2

题目链接

给定全为2的幂次序列,判断能否用序列中数字组成给定的数,若能输出选择最少数字的个数,不能输出-1。

贪心,尽可能选择大的数字。

AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4+5;
const int mod = 1e6;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n, q;
    read(n); read(q);
    int x;
    map<int, int> amount;
    for (int i = 0; i < n; ++i) {
        read(x);
        amount[x]++;
    }
    int cnt;
    for (int i = 0; i < q; ++i) {
        read(x);
        cnt = 0;
        for (int j = 29; j >= 0; --j) {
            int num = (1 << j);
            if (num <= x) {
                int temp = x / num;
                if (temp <= amount[num]) {
                    cnt += temp;
                    x -= num * temp;
                }
                else {
                    cnt += amount[num];
                    x -= amount[num] * num;
                }
            }
        }
        if (!x) {
            printf("%d\n", cnt);
        }
        else {
            printf("-1\n");
        }
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("gedit out.txt");
#endif
    return 0;
}

E. Tree Constructing

题目:

You are given three integers n, d and k.
Your task is to construct an undirected tree on n vertices with diameter d and degree of each vertex at most k, or say that it is impossible.
An undirected tree is a connected undirected graph with n1 edges.
Diameter of a tree is the maximum length of a simple path (a path in which each vertex appears at most once) between all pairs of vertices of this tree.
Degree of a vertex is the number of edges incident to this vertex (i.e. for a vertex u it is the number of edges (u,v) that belong to the tree, where v is any other vertex of a tree).

Input:

The first line of the input contains three integers n, d and k (1n,d,k4105).

Output

If there is no tree satisfying the conditions above, print only one word “NO” (without quotes).
Otherwise in the first line print “YES” (without quotes), and then print n1 lines describing edges of a tree satisfying the conditions above. Vertices of the tree must be numbered from 1 to n. You can print edges and vertices connected by an edge in any order. If there are multiple answers, print any of them.1

Sample Input:

6 3 3

Sample Output:

YES
3 1
4 1
1 2
5 2
2 6

Sample Input:

6 2 3

Sample Output:

NO

Sample Input:

10 4 3

Sample Output:

YES
2 9
2 10
10 3
3 1
6 10
8 2
4 3
5 6
6 7

Sample Input:

8 5 3

Sample Output:

YES
2 5
7 2
3 7
3 1
1 6
8 7
4 3

题目链接

用n个顶点建立一个最大直径为d,最大度数为k的树。

先用前d+1个点连接出最大直径,然后在可添加边的顶点上添加其它顶点,并实时更新判断直径和度数。

AC代码:

#pragma comment(linker, "/STACK:102400000,102400000")
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 4e5+5;
const int mod = 1e9+7;
const double eps = 1e-8;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int n, d, k;
    read(n); read(d); read(k);
    if (d >= n) {
        printf("NO\n");
        return 0;
    }
    // 度数
    vector<int> deg(n);
    // 连接结果
    vector<PII> ans;
    // 顶点和直径
    set<PII> q;
    for (int i = 0; i < d; ++i) {
        ++deg[i];
        ++deg[i + 1];
        if (deg[i] > k || deg[i + 1] > k) {
            printf("NO\n");
            return 0;
        }
        ans.pb(mp(i, i + 1));
    }
    // 以此插入顶点和顶点直径
    for (int i = 1; i < d; ++i) {
        q.insert(mp(max(i, d - i), i));
    }
    for (int i = d + 1; i < n; ++i) {
        // 若有顶点且不可再连,移除
        while (!q.empty() && deg[q.begin() -> second] == k) {
            q.erase(q.begin());
        }
        // 若无顶点可连或可连顶点直径为最大值,无解
        if (q.empty() || q.begin() -> first == d) {
            printf("NO\n");
            return 0;
        }
        ++deg[i];
        ++deg[q.begin() -> second];
        ans.pb(mp(i, q.begin() -> second));
        q.insert(mp(q.begin() -> first + 1, i));
    }
    printf("YES\n");
    for (int i = 0; i < n - 1; ++i) {
        printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
    fclose(stdout);
    system("gedit out.txt");
#endif
    return 0;
}

F. Abbreviation

题目:

You are given a text consisting of n space-separated words. There is exactly one space character between any pair of adjacent words. There are no spaces before the first word and no spaces after the last word. The length of text is the number of letters and spaces in it. wi is the i-th word of text. All words consist only of lowercase Latin letters.
Let’s denote a segment of words w[i..j] as a sequence of words wi,wi+1,,wj. Two segments of words w[i1..j1] and w[i2..j2] are considered equal if j1i1=j2i2, j1i1, j2i2, and for every t[0,j1i1] wi1+t=wi2+t. For example, for the text “to be or not to be” the segments w[1..2] and w[5..6] are equal, they correspond to the words “to be”.
An abbreviation is a replacement of some segments of words with their first uppercase letters. In order to perform an abbreviation, you have to choose at least two non-intersecting equal segments of words, and replace each chosen segment with the string consisting of first letters of the words in the segment (written in uppercase). For example, for the text “a ab a a b ab a a b c” you can replace segments of words w[2..4] and w[6..8] with an abbreviation “AAA” and obtain the text “a AAA b AAA b c”, or you can replace segments of words w[2..5] and w[6..9] with an abbreviation “AAAB” and obtain the text “a AAAB AAAB c”.
What is the minimum length of the text after at most one abbreviation?

Input:

The first line of the input contains one integer n (1n300) — the number of words in the text.
The next line contains n space-separated words of the text w1,w2,,wn. Each word consists only of lowercase Latin letters.
It is guaranteed that the length of text does not exceed 105.

Output

Print one integer — the minimum length of the text after at most one abbreviation.

Sample Input:

6
to be or not to be

Sample Output:

12

Sample Input:

10
a ab a a b ab a a b c

Sample Output:

13

Sample Input:

6
aa bb aa aa bb bb

Sample Output:

11

题目链接

题都看不懂……先放个官方题解吧

AC代码:

#include <bits/stdc++.h>

using namespace std;

const int N = 303;

int n;
bool eq[N][N];
int dp[N][N];
string s[N];

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif

    cin >> n;
    int allsum = n - 1;
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
        allsum += s[i].size();
    }

    for (int i = 0; i < n; ++i) {
        eq[i][i] = true;
        for (int j = 0; j < i; ++j) {
            eq[i][j] = eq[j][i] = s[i] == s[j];
        }
    }

    for (int i = n - 1; i >= 0; --i) {
        for (int j = n - 1; j >= 0; --j) {
            if (eq[i][j]) {
                if (i + 1 < n && j + 1 < n)
                    dp[i][j] = dp[i + 1][j + 1] + 1;
                else
                    dp[i][j] = 1;
            }
        }
    }

    int ans = allsum;
    for (int i = 0; i < n; ++i) {
        int sum = 0;
        for (int j = 0; i + j < n; ++j) {
            sum += s[i + j].size();
            int cnt = 1;
            for (int pos = i + j + 1; pos < n; ++pos) {
                if (dp[i][pos] > j) {
                    ++cnt;
                    pos += j;
                }
            }
            int cur = allsum - sum * cnt + (j + 1) * cnt - j * cnt;
            if (cnt > 1 && ans > cur) {
                ans = cur;
            }
        }
    }

    cout << ans << endl;

    return 0;
}
版权声明:本文为Tony5t4rk原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Tony5t4rk/article/details/81104766

智能推荐

phpstudy的mysql版本升级至5.7

phpstudy安装的mysql版本一般都是5.5或5.4的,但是有时候做项目又必须用到mysql5.7版本,所以我们现在来看一下如何在phpstudy的环境下将mysql版本升级至5.7   温馨提醒: 先删掉所有环境变量,如果是之前有的话,不然怎么安装cmd上指向的还是原来的版本。安装完再设新的环境变量。 并且卸载掉mysqld服务mysqld remove。如果不先删除的话,可能会...

RIP/DHCP/ACL综合实验

组播: 加入组的组成员才会接受到消息,只需要将流量发送一次到组播地址 减少控制面流量,减少头部复制, RIP1  广播   有类  不支持认证 RIP2  组播   无类  (支持VLAN)、支持认证 所有距离矢量路由协议:具有距离矢量特征的协议,都会在边界自动汇总 控制平面  路由的产生是控制平面的流量 数据平面  ...

【Sublime】使用 Sublime 工具时运行python文件

使用 Sublime 工具时报Decode error - output not utf-8解决办法   在菜单中tools中第四项编译系统 内最后一项增添新的编译系统 自动新建 Python.sublime-build文件,并添加"encoding":"cp936"这一行,保存即可 使用python2 则注释encoding改为utf-8 ctr...

java乐观锁和悲观锁最底层的实现

1. CAS实现的乐观锁 CAS(Compare And Swap 比较并且替换)是乐观锁的一种实现方式,是一种轻量级锁,JUC 中很多工具类的实现就是基于 CAS 的,也可以理解为自旋锁 JUC是指import java.util.concurrent下面的包, 比如:import java.util.concurrent.atomic.AtomicInteger; 最终实现是汇编指令:lock...

Python 中各种imread函数的区别与联系

  原博客:https://blog.csdn.net/renelian1572/article/details/78761278 最近一直在用python做图像处理相关的东西,被各种imread函数搞得很头疼,因此今天决定将这些imread总结一下,以免以后因此犯些愚蠢的错误。如果你正好也对此感到困惑可以看下这篇总结。当然,要了解具体的细节,还是应该 read the fuc...

猜你喜欢

用栈判断一个字符串是否平衡

注: (1)本文定义:左符号:‘(’、‘[’、‘{’…… 右符号:‘)’、‘]’、‘}’……. (2)所谓的字符串的符号平衡,是指字符串中的左符号与右符号对应且相等,如字符串中的如‘(&r...

JAVA环境变量配置

位置 计算机->属性->高级系统设置->环境变量 方式一 用户变量新建path 系统变量新建classpath 方式二 系统变量 新建JAVA_HOME,值为JDK路径 编辑path,前加 方式三 用户变量新建JAVA_HOME 此路径含lib、bin、jre等文件夹。后运行tomcat,eclipse等需此变量,故最好设。 用户变量编辑Path,前加 系统可在任何路径识别jav...

常用的伪类选择器

CSS选择器众多 CSS选择器及权重计算 最常用的莫过于类选择器,其它的相对用的就不会那么多了,当然属性选择器和为类选择器用的也会比较多,这里我们就常用的伪类选择器来讲一讲。 什么是伪类选择器? CSS伪类是用来添加一些选择器的特殊效果。 常用的为类选择器 状态伪类 我们中最常见的为类选择器就是a标签(链接)上的为类选择器。 当我们使用它们的时候,需要遵循一定的顺序问题,否则将可能出现bug 注意...

ButterKnife的使用介绍及原理探究(六)

前面分析了ButterKnife的源码,了解其实现原理,那么就将原理运用于实践吧。 github地址:       点击打开链接 一、自定义注解 这里为了便于理解,只提供BindView注解。 二、添加注解处理器 添加ViewInjectProcessor注解处理器,看代码, 这里分别实现了init、getSupportedAnnotationTypes、g...

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。考试复习题库1|要求:只能使用单字符比较操作。

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。 要求只能使用单字符比较操作。 参考代码: 实验结果截图:...