130331周赛

A. Roma and Changing Signs

此题最希望的是能把所有的负数都变成正数，当负数个数>=操作数，由小到大变正；当负数个数<操作数时，剩下的操作数只对最小的操作。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int n,k;
int a[100005];

int main()
{
    int i,j;
    while(cin >> n >> k)
    {
        int cnt = 0;
        for(i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
            if(a[i] < 0)
                cnt ++;
        }
        if(cnt >= k)
        {
            for(i=0; i<k; i++)
                a[i] = -a[i];
        }
        int t = 0;
        if(cnt < k)
        {
            for(i=0; i<cnt; i++)
                a[i] = -a[i];
            t = (k - cnt) % 2;
            sort(a,a+n);
            if(t == 1)
                a[0] = -a[0];
        }
        long long sum = 0;
        for(i=0; i<n; i++)
            sum += a[i];
        cout << sum << endl;
    }
    return 0;
}

B. Maxim and Discounts

活动有几种，买n送2,贪心的角度，选择n最小的。因为送的两件商品价格必须低于买的n件，所以将商品从大到小排序。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int n,m;
int a[100005],q[100005];

bool cmp(int a,int b)
{
    return a > b;
}
int main()
{
    int i,j;
    while(cin >> m)
    {
        int minm = 100000000;
        for(i=0; i<m; i++)
        {
            scanf("%d",&q[i]);
            if(minm > q[i])
                minm = q[i];
        }
        cin >> n;
        for(i=0; i<n; i++)
            scanf("%d",&a[i]);
        sort(a,a+n,cmp);

        int sum = 0,cnt = minm,tmp = 0;
        for(int i=0; i<n; i++)
        {
            if(tmp > 0)
            {
                tmp --;
                cnt = minm;
                continue;
            }
            cnt --;
            if (cnt == 0)
                tmp = 2;
            sum += a[i];
        }
        cout << sum << endl;
    }
    return 0;
}

D. Squares

水题，看完就能做了

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

bool cmp(int a,int b)
{
    return a >b;
}

int a[55];
int n,k;
int main()
{
    int i;
    while(cin >> n >> k)
    {
        for(i=1; i<=n; i++)
            cin >> a[i];
        if(k > n)
        {
            cout << -1 << endl;
            continue;
        }
        sort(a+1,a+n+1,cmp);
        cout << a[k] << ' ' << a[k] << endl;
    }
    return 0;
}

F. Cycle in Graph

在图中找出环......

先dfs找出一条链，然后从开头开始判断与尾部是否相连

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#define MAX 100010
using namespace std;

bool vis[MAX],neigh[MAX];
vector<int>a[MAX];
vector<int>lis;
int n,m,k;

void dfs(int x)
{
    vis[x] = 1;
    lis.push_back(x);
    for(int i=0; i<a[x].size(); i++)
    {
        if(vis[a[x][i]] == 1)
            continue;
        vis[a[x][i]] = 1;
        dfs(a[x][i]);
        break;
    }
}

int main()
{
    int i,j,b,c;
    while(cin >> n >> m >> k)
    {
        memset(vis,0,sizeof(vis));
        memset(neigh,0,sizeof(neigh));
        lis.clear();
        for(i=0;i<MAX; i++)
            a[i].clear();
        for(i=0; i<m; i++)
        {
            scanf("%d%d",&b,&c);
            a[b].push_back(c);
            a[c].push_back(b);
        }
        dfs(1);
        int t = lis.back();
        for(i=0; i<a[t].size(); i++)
        {
            neigh[a[t][i]] = 1;
        }
        while(neigh[lis[0]] == 0)
            lis.erase(lis.begin());
        cout << lis.size() << endl;
        for(i=0; i<lis.size(); i++)
            cout << lis[i] << ' ';
        cout << endl;
    }
    return 0;
}

G. Roadside Trees (Simplified Edition)

水题直接模拟

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;
int n;

int main()
{
    int a;
    int sum=0,b=0;
    cin >> n;
    while (n--)
    {
        scanf("%d",&a);
        sum++;
        if(a > b)
            sum += (a-b);
        else if(b > a)
            sum += (b-a);
        sum++;
        b = a;
    }
    
    printf("%d\n",sum-1);
    return 0;
}

H. Escape from Stones

题目的叙述是二分的思想，可以推断 ：第一次向右边跳时，原所在点肯定是总的边界的最左边（以后不会更靠左边），同理，第一次向左跳时，原所在点为最右端。

直接根据输入输出

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
char a[1000005];

int main()
{
    cin >> a;
    int len = strlen(a);
    for(int i=0; i<len; i++)
    {
        if(a[i] == 'r')
            cout << i+1 << endl;
    }
    for(int i=len-1; i>=0; i--)
    {
        if(a[i] == 'l')
            cout << i+1 << endl;
    }
    return 0;
}

I. Good Sequences

此题直接用o(n^2)的dp铁定超时，但还是忍不住交了一发

参考了CF的代码，预先将所有不互质的关系保存好。然后从遍历，dp[i] = max(dp[p[i][j]]+1,dp[i])

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int a[100005],good[100005],dp[100005];
int n;

vector<int>p[100005];

int main()
{
    int i,j;
    while(cin >> n)
    {
        int maxn = 0;
        memset(good,0,n);
        memset(dp,0,sizeof(dp));
        for(i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
            maxn = max(a[i],maxn);
            good[a[i]] = 1;
        }
        for(i=2; i<=maxn; i++)
        {
            int tmp = 0;
            for(j=i; j<=maxn; j+=i)
            {
                if(good[j] == 1)
                {
                    if(tmp != 0)
                        p[j].push_back(tmp);
                    tmp = j;
                }
            }
        }
        int ans = 1;
        for(i=2; i<=maxn; i++)
        {
            if(good[i] == 1)
            {
                dp[i] = 1;
                for(j=0; j<p[i].size(); j++)
                {
                    dp[i] = max(dp[p[i][j]]+1,dp[i]);
                }
                ans = max(dp[i],ans);
            }
        }
        cout << ans << endl;
    }
    return 0;
}