codeforces

A. Anastasia and pebbles

题意：
给你n种小石块，数目确定，你每次每只手只能拿k个小石块，每只手只能拿一种小石块，问多少次拿完。

思路：
贪心。
排序后从最少的开始取。我们设当前你要取的石头堆的剩余石头为cur，每次拿取有如下几种情况:

• cur<=k 全部取走，并让另一只手去重新讨论下一堆石头
• k < cur < 2*k 两只手全部取走 所取石头堆往后移
• cur>2*k 两只手全部取走 当前讨论石头堆不变

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <queue>
#include <set>
#include <string>

#define ll long long

using namespace std;
const double eps = 1e-6;
const int maxn = 100010;
const int inf = 0x3f3f3f3f;

int n, m;
int arr[maxn];

int main()
{
    while (scanf("%d %d", &n, &m) != EOF) {
        for (int i = 0; i < n; i++)
            scanf("%d", arr + i);
        sort(arr,arr+n);
        int idx=0,ans=0;
        while(idx<n)
        {
            ans++;
            if(arr[idx]<=m){
                idx++;
                if(idx>=n)
                    break;
                if(arr[idx]<=m)
                    idx++;
                else
                    arr[idx]-=m;
            }
            else {
                arr[idx]-=m;
                if(arr[idx]<=m)
                    idx++;
                else
                    arr[idx]-=m;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

B. Masha and geometric depression

题意:
给你一个等比数列和数组，并给你一个上界，要你要上界之下 输出 不属于这个数组的 等比数列的所有数

思路:
题目不难，就是情况有点多，不知道怎么快速，清晰的表达
我这里用了两个set group 和 vis ，group存数组，vis存 已遍历的 等比数列的项
如果不考虑特殊情况的话，就只是两个集合之间的运算，这就不多说了。这里说一下我对特殊情况的考虑和处理。
特殊情况分为:

• b=0 q=?
• b=? q=0
• b=? q=-1

但无论哪种情况，都会出现重复的元素。如果出现重复的元素，如果group内存在这个重复元素，就直接输出记录结果，否则输出inf。
但是第三种 -1 的情况会有点特殊，它可以在-b 和 b 之间不停跳转，这时候就得查找 -b 是否也在group内，如果存在，就输出记录结果，不存在就输出inf。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <queue>
#include <set>
#include <string>

#define ll long long

using namespace std;
const double eps = 1e-6;
const int maxn = 100010;
const int inf = 0x3f3f3f3f;

ll b, q, l, m;
set<int> group;
set<int> vis;

int main()
{
    int tmp;
    while (scanf("%lld %lld %lld %lld", &b, &q, &l, &m) != EOF) {
        group.clear();
        vis.clear();
        for (int i = 0; i < m; i++) {
            scanf("%d", &tmp);
            group.insert(tmp);
        }
        int ans = 0;
        bool flag = false;
        while (abs(b) <= l) {
            if (vis.find(b) != vis.end()) {
                if (group.find(b) != group.end() && (q != -1 || group.find(-b) != group.end()))
                    printf("%d\n", ans);
                else
                    puts("inf");
                flag = true;
                break;
            }
            vis.insert(b);
            if (group.find(b) == group.end())
                ans++;
            b *= q;
        }
        if (!flag)
            printf("%d\n", ans);
    }
    return 0;
}

C. Functions again

题意：
给你一个数组，如下公式，让你求最大的 f(l,r)

思路：
把数组内所有数都转化一下 再求连续最大和即可（比B题简单多了

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

long long arr[100100];

long long MaxSubArray(long long a[], long long len)
{
    long long maxsum, maxhere;
    maxsum = maxhere = a[0]; 
    for (int i = 1; i < len; i++) {
        if (maxhere <= 0)
            maxhere = a[i]; 
        else
            maxhere += a[i]; 
        if (maxhere > maxsum) {
            maxsum = maxhere; 
        }
    }
    return maxsum;
}
int main()
{
    int n;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++)
            scanf("%lld", arr + i);
        int key = 1;
        for (int i = 0; i < n - 1; i++) {
            arr[i] = abs(arr[i] - arr[i + 1]) * key;
            key *= -1;
        }
        long long ans = MaxSubArray(arr,n-1);
        for(int i=0;i<n-1;i++)
            arr[i]*=-1;
        printf("%lld\n",max(ans,MaxSubArray(arr, n - 1)));
    }
    return 0;
}

D. Weird journey

**note：**这题我自己也搞不明白，最好先别看，大神只给了我代码，我现在也理解不了

题意：
给你一个n,表示点数,m,表示边数目，m条边，构建成无向图，要你求出满足如下要求的路径数目。
任意起点，终点，满足路径上，有两条边只走过一次，其他m-2走过两次。
起点和终点不同即是路径不同，但如果起点0=终点1 终点0=起点1 则0 ，1 视为同一路径

思路：
无( 玛德，只给我代码，白白看了2个小时还看不懂。

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

const int maxn = 1000000 + 10;
int root[maxn];

int findRoot(int a)
{
    if (root[a] == a)
        return a;
    return root[a] = findRoot(root[a]);
}

bool join(int a, int b)
{
    a = findRoot(a);
    b = findRoot(b);
    if (a == b)
        return false;
    root[b] = a;
    return true;
}

int64 dg[maxn];
bool seen[maxn];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int64 n, m;
    cin >> n >> m;
    int tot = 0;    //出现的点数
    int cmp = n;    //点集数

    for (int i = 0; i < n; ++i) {
        root[i] = i;
    }

    int64 loop = 0;  //自环数
    int64 ans = 0;

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;

        if (u == v) {
            ans += m - ++loop; //不是很懂这个地方
            if (!seen[u])
                tot++;
            seen[u] = true;
            continue;
        }

        if (!seen[u])
            tot++;
        dg[u]++;
        seen[u] = true;
        if (!seen[v])
            tot++;
        seen[v] = true;
        dg[v]++;
        if (join(u, v))
            cmp--;      
    }

    if (cmp != n - tot + 1) {
        cout << 0 << endl;
        return 0;
    }

    for (int i = 0; i < n; ++i)
        ans += dg[i] * (dg[i] - 1) / 2;

    cout << ans << endl;

    return 0;
}

如果有看懂的朋友记得跟我说一声……

E. The Great Mixing

（暂缺）