Codeforces Round #358 (Div. 2) A B C D - dblank

Codeforces Round #358 (Div. 2) A B C D

<h2>A. Alyona and Numbers</h2>
<div>

After finishing eating her bun, Alyona came up with two integers <span class="tex-span">n</span> and <span class="tex-span">m</span>. She decided to write down two columns of integers — the first column containing integers from <span class="tex-span">1</span> to <span class="tex-span">n</span> and the second containing integers from <span class="tex-span">1</span> to <span class="tex-span">m</span>. Now the girl wants to count how many pairs of integers she can choose, one from the first column and the other from the second column, such that their sum is divisible by <span class="tex-span">5</span>.

Formally, Alyona wants to count the number of pairs of integers <span class="tex-span">(x, y)</span> such that <span class="tex-span">1 ≤ x ≤ n</span>, <span class="tex-span">1 ≤ y ≤ m</span> and equals <span class="tex-span">0</span>.

As usual, Alyona has some troubles and asks you to help.

</div>
<div class="input-specification">
<div class="section-title">Input</div>
The only line of the input contains two integers <span class="tex-span">n</span> and <span class="tex-span">m</span> (<span class="tex-span">1 ≤ n, m ≤ 1 000 000</span>).

</div>
<div class="output-specification">
<div class="section-title">Output</div>
Print the only integer — the number of pairs of integers <span class="tex-span">(x, y)</span> such that <span class="tex-span">1 ≤ x ≤ n</span>, <span class="tex-span">1 ≤ y ≤ m</span> and <span class="tex-span">(x + y)</span> is divisible by <span class="tex-span">5</span>.

</div>
<div class="sample-tests">
<div class="section-title">题意:给你一个n和m,你有多少对满足1<=x<=n和1<=y<=m并且(x+y)%5==0的 数对.</div>
<div class="section-title">思路:因为n和m很大所以不能循环,我们可以枚举x,对于一个一定是((y%5)+ (x%5))%5==0,于是可以得对于每一个x,都有(m+(x%5))/5个对应的y。</div>
<div class="section-title">代码:</div>
<div class="section-title">

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 3e1 + 10, Mod = 1000000007;
typedef long long ll;
int main()
{
    ll ans = 0;
    int n, m;
    while(cin>>n>>m)
    {
        ans = 0;
        for(int i = 1; i<=n; i++)
        {
            ans += (m+(i%5))/5;
        }
        cout<<ans<<endl;
    }
    return 0;
}

<h2>B. Alyona and Mex</h2>
<div>

Someone gave Alyona an array containing <span class="tex-span">n</span> positive integers <span class="tex-span">a1, a2, ..., an</span>. In one operation, Alyona can choose any element of the array and decrease it, i.e. replace with any positive integer that is smaller than the current one. Alyona can repeat this operation as many times as she wants. In particular, she may not apply any operation to the array at all.

Formally, after applying some operations Alyona will get an array of <span class="tex-span">n</span> positive integers <span class="tex-span">b1, b2, ..., bn</span> such that <span class="tex-span">1 ≤ bi ≤ ai</span> for every<span class="tex-span">1 ≤ i ≤ n</span>. Your task is to determine the maximum possible value of mex of this array.

<span class="tex-font-style-it">Mex</span> of an array in this problem is the <span class="tex-font-style-bf">minimum positive</span> integer that doesn't appear in this array. For example, mex of the array containing <span class="tex-span">1</span>, <span class="tex-span">3</span> and <span class="tex-span">4</span> is equal to <span class="tex-span">2</span>, while mex of the array containing <span class="tex-span">2</span>, <span class="tex-span">3</span> and <span class="tex-span">2</span> is equal to <span class="tex-span">1</span>.

</div>
<div class="input-specification">
<div class="section-title">Input</div>
The first line of the input contains a single integer <span class="tex-span">n</span> (<span class="tex-span">1 ≤ n ≤ 100 000</span>) — the number of elements in the Alyona's array.

The second line of the input contains <span class="tex-span">n</span> integers <span class="tex-span">a1, a2, ..., an</span> (<span class="tex-span">1 ≤ ai ≤ 109</span>) — the elements of the array.

</div>
<div class="output-specification">
<div class="section-title">Output</div>
Print one positive integer — the maximum possible value of mex of the array after Alyona applies some (possibly none) operations.

题意:给你一个数列,你可以让每一个ai都变成bi, bi满足1<=bi<=ai,你也可以不操作,问你在操作后最小的没出现的数最大是多少。

这里的最小的没出现的意思是从1开始直到不在b数列里面的那个数。

思路:我们可以得到这个最大一定是把b变成没有空隙的数列后最大的那个元素+1.

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e5 + 10, Mod = 1000000007;
typedef long long ll;
int a[N];
int main()
{
    int n;
    while(cin>>n)
    {
        for(int i = 0; i<n; i++)
            scanf("%d", &a[i]);
        sort(a, a+n);
        int k = 1;
        for(int i = 0; i<n; i++)
        {
            if(a[i] >= k)
                k++;
        }
        cout<<k<<endl;
    }
    return 0;
}

<h2>C. Alyona and the Tree</h2>
<div>

Alyona decided to go on a diet and went to the forest to get some apples. There she unexpectedly found a magic rooted tree with root in the vertex <span class="tex-span">1</span>, every vertex and every edge of which has a number written on.

The girl noticed that some of the tree's vertices are <span class="tex-font-style-it">sad</span>, so she decided to play with them. Let's call vertex <span class="tex-span">v</span> <span class="tex-font-style-it">sad</span> if there is a vertex <span class="tex-span">u</span> in subtree of vertex <span class="tex-span">v</span> such that <span class="tex-span">dist(v, u) > au</span>, where <span class="tex-span">au</span> is the number written on vertex <span class="tex-span">u</span>, <span class="tex-span">dist(v, u)</span> is the sum of the numbers written on the edges on the path from <span class="tex-span">v</span> to <span class="tex-span">u</span>.

<span class="tex-font-style-it">Leaves</span> of a tree are vertices connected to a single vertex by a single edge, but the root of a tree is a <span class="tex-font-style-it">leaf</span> if and only if the tree consists of a single vertex — root.

Thus Alyona decided to remove some of tree leaves until there will be no any sad vertex left in the tree. What is the minimum number of leaves Alyona needs to remove?

</div>
<div class="input-specification">
<div class="section-title">Input</div>
In the first line of the input integer <span class="tex-span">n</span> (<span class="tex-span">1 ≤ n ≤ 105</span>) is given — the number of vertices in the tree.

In the second line the sequence of <span class="tex-span">n</span> integers <span class="tex-span">a1, a2, ..., an</span> (<span class="tex-span">1 ≤ ai ≤ 109</span>) is given, where <span class="tex-span">ai</span> is the number written on vertex <span class="tex-span">i</span>.

The next <span class="tex-span">n - 1</span> lines describe tree edges: <span class="tex-span">ith</span> of them consists of two integers <span class="tex-span">pi</span> and <span class="tex-span">ci</span> <span class="tex-span">(1 ≤ pi ≤ n</span>, <span class="tex-span"> - 109 ≤ ci ≤ 109)</span>, meaning that there is an edge connecting vertices <span class="tex-span">i + 1</span> and <span class="tex-span">pi</span> with number <span class="tex-span">ci</span> written on it.

</div>
<div class="output-specification">
<div class="section-title">Output</div>
<div class="section-title">Print the only integer — the minimum number of leaves Alyona needs to remove such that there will be no any sad vertex left in the tree.</div>
<div class="section-title">题意:给你一颗树,这颗树上的每一个点都有一个权值,没一条边都有一个权值。如果一个节点的子节点到它的边权之和大于这个子节点的点权,那这个父节点就是一个sad,问你删除最少的节点是没有sad节点。</div>
<div class="section-title">思路:如果这个节点到他的任意一个祖先节点的边权和大于它本身的点权,那么以它为根的子树都要被删除。我们可以从根节点bfs直接找到每一个节点到它的祖先节点的最大路径长度。这样可以找到不是sad的点最多少,减一下就是的答案.</div>
<div class="section-title">代码:</div>
<div class="section-title">

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e5 + 10, Mod = 1000000007;
typedef long long ll;
int a[N], n, ans, vis[N];
struct node
{
    int to, x;
};
vector<node> path[N];
ll dp[N];
void bfs(int fa)
{
    int x, y;
    queue<int>q;
    q.push(fa);
    memset(vis, 0, sizeof(vis));
    vis[fa] = 1;
    ans = 1;
    memset(dp, 0, sizeof(dp));
    while(!q.empty())
    {
        x = q.front();
        q.pop();
        for(int i = 0, sz = path[x].size(); i<sz; i++)
        {
            y = pathx.to;
            if(!vis[y])
            {
                dp[y] = max(dp[x] + pathx.x, dp[y]);
                if(dp[y] > a[y])
                    continue;
                q.push(y);
                ++ans;
                vis[y] = 1;
            }
        }
    }
}
int main()
{
    while(~scanf("%d", &n))
    {
        ans = 0;
        for(int i = 1; i<=n; i++)
            path[i].clear();
        for(int i = 1; i<=n; i++)
            scanf("%d", &a[i]);
        int u, v;
        node in;
        for(int i = 1; i<n; i++)
        {
            scanf("%d%d", &u, &v);
            in.to = i+1;
            in.x = v;
            path[u].push_back(in);
            in.to = u;
            path[i+1].push_back(in);
        }
        bfs(1);
        cout<<n-ans<<endl;
    }
    return 0;
}

<h2>D. Alyona and Strings</h2>
<div>

After returned from forest, Alyona started reading a book. She noticed strings <span class="tex-span">s</span> and <span class="tex-span">t</span>, lengths of which are <span class="tex-span">n</span> and <span class="tex-span">m</span> respectively. As usual, reading bored Alyona and she decided to pay her attention to strings <span class="tex-span">s</span> and <span class="tex-span">t</span>, which she considered very similar.

Alyona has her favourite positive integer <span class="tex-span">k</span> and because she is too small, <span class="tex-span">k</span> does not exceed <span class="tex-span">10</span>. The girl wants now to choose <span class="tex-span">k</span> disjoint non-empty substrings of string <span class="tex-span">s</span> such that these strings appear as disjoint substrings of string <span class="tex-span">t</span> and in the same order as they do in string <span class="tex-span">s</span>. She is also interested in that their length is maximum possible among all variants.

Formally, Alyona wants to find a sequence of <span class="tex-span">k</span> non-empty strings <span class="tex-span">p1, p2, p3, ..., pk</span> satisfying following conditions:

  • <span class="tex-span">s</span> can be represented as concatenation <span class="tex-span">a1p1a2p2... akpkak + 1</span>, where <span class="tex-span">a1, a2, ..., ak + 1</span> is a sequence of arbitrary strings (some of them may be possibly empty);
  • <span class="tex-span">t</span> can be represented as concatenation <span class="tex-span">b1p1b2p2... bkpkbk + 1</span>, where <span class="tex-span">b1, b2, ..., bk + 1</span> is a sequence of arbitrary strings (some of them may be possibly empty);
  • sum of the lengths of strings in sequence is maximum possible.

Please help Alyona solve this complicated problem and find at least the sum of the lengths of the strings in a desired sequence.

A <span class="tex-font-style-it">substring</span> of a string is a subsequence of consecutive characters of the string.

</div>
<div class="input-specification">
<div class="section-title">Input</div>
In the first line of the input three integers <span class="tex-span">n</span>, <span class="tex-span">m</span>, <span class="tex-span">k</span> (<span class="tex-span">1 ≤ n, m ≤ 1000</span>, <span class="tex-span">1 ≤ k ≤ 10</span>) are given — the length of the string <span class="tex-span">s</span>, the length of the string <span class="tex-span">t</span> and Alyona's favourite number respectively.

The second line of the input contains string <span class="tex-span">s</span>, consisting of lowercase English letters.

The third line of the input contains string <span class="tex-span">t</span>, consisting of lowercase English letters.

</div>
<div class="output-specification">
<div class="section-title">Output</div>
In the only line print the only non-negative integer — the sum of the lengths of the strings in a desired sequence.

<span class="tex-font-style-bf">It is guaranteed</span>, that at least one desired sequence exists.

题意:给你两个字符串,让你把每一个都找到不相交的k段子串,并且两个字符串的子串一一相等,问你最长的k段子串总长度.

思路:如果s[i] == t[j] 那么我们可以找到s[i] 和t[j]结尾的最长相等子串的长度,先把这个表打出,那我们还可以以ansi[r]表示s串的前i和t串的钱j个已经划成了r段的最长子串长度总和。状态转移一下即可。

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
using namespace std;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f, N = 1e3 + 10, Mod = 1000000007;
typedef long long ll;
char s[N], t[N];
int dpN, ansN[12];
int main()
{
    int n, m, k;
    while(cin>>n>>m>>k)
    {
        scanf("%s", s+1);
        scanf("%s", t+1);
        memset(dp, 0, sizeof(dp));
        memset(ans, 0, sizeof(ans));
        for(int i = 1; i<=n; i++)
            for(int j = 1; j<=m; j++)
            {
                if(s[i] == t[j])
                    dpi = dpi-1 + 1;
            }
        for(int i = 1; i<=n; i++)
            for(int j = 1; j<=m; j++)
                for(int r = 1; r<=k; r++)
                {
                    ansi[r] = max(ansi[r], ansi-1[r]);
                    if(dpi)
                        ansi[r] = max(ansi[r],
                                           ansi-dp[i]j-dp[i][r-1] + dpi);
                }
        cout<<ansn[k]<<endl;
    }
    return 0;
}

 

</div>
</div>
</div>
</div>
</div>
</div>

相关文章

发表新评论