130331周賽

A. Roma and Changing Signs
此題最希望的是能把所有的負數都變成正數，當負數個數>=操作數，由小到大變正；當負數個數<操作數時，剩下的操作數只對最小的操作。

[cpp] 
#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; 
} 

#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件，所以將商品從大到小排序。

[cpp] 
#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; 
} 

#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
水題，看完就能做了

[cpp]
#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; 
} 

#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找出一條鏈，然後從開頭開始判斷與尾部是否相連
[cpp]
#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; 
} 

#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)
水題直接模擬

[cpp] 
#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; 
} 

#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
題目的敘述是二分的思想，可以推斷 ：第一次向右邊跳時，原所在點肯定是總的邊界的最左邊（以後不會更靠左邊），同理，第一次向左跳時，原所在點為最右端。
直接根據輸入輸出

[cpp] 
#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; 
} 

#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])

[cpp] 
#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; 
} 

#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;
}