程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Round #288 (Div. 2) A,B,C,D,E

Codeforces Round #288 (Div. 2) A,B,C,D,E

編輯:C++入門知識

Codeforces Round #288 (Div. 2) A,B,C,D,E


A:一個一個點向圖裡面加,判斷其所在的位置與其他的點是否可以構成小矩形就可以了。

B:貪心,如果前面的偶數有比他小的就找到一個最靠前的交換,如果前面的偶數都比它小,就找一個最靠後的交換。

C:貪心,把蠟燭盡可能的放在惡魔,來之前,這樣可以充分利用蠟燭的時間,模擬一下,不停地向前方就可以了。如果蠟燭時間小於需要的數目,一定不可以。

const int maxn = 2010;


int vis[maxn];
int num[maxn];

int main()
{
    int m, t, r;
    while(cin >>m>>t>>r)
    {
        for(int i = 1; i <= m; i++)
            scanf("%d",&num[i]);
        if(r > t)
        {
            puts("-1");
            continue;
        }
        int ans = 0;
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= m; i++)
        {
            int x = num[i]-1;
            while(vis[num[i]+1000] < r)
            {
                for(int k = x-1; k <= x+t; k++)
                    vis[k+1000]++;
                ans++;
                x --;
            }
        }
        cout<
D:歐拉路徑+打印路徑。

判斷歐拉路徑的方法是,統計出來他的度(入度+, 出度-)。如果所有的度均為0,或者只有一對度數為(+1,-1)的,那麼就可以構成路徑。但是這題還必須保證字符串的數目,所以判斷之後,還有跑一遍dfs求出長度,判斷長度是否滿足條件。

打印路徑的時候,先dfs再保存邊,這樣可以保證一開始存的邊一定是距離“起點”最遠的。

const int maxn = 200010;
char str[maxn][10];

int deg[maxn];
int ans[maxn];
int vis[maxn];
int cur[maxn];

vector > G[maxn*3];

int cnt;

int Get(char x)
{
    if ('0' <= x && x <= '9')return x-'0';
    if ('a' <= x && x <= 'z')return x-'a'+10;
    return x-'A'+36;
}

int get_x(int x)
{
    return Get(str[x][0])*62+Get(str[x][1]);
}

int get_y(int y)
{
    return Get(str[y][1])*62+Get(str[y][2]);
}

void dfs(int x, int y)
{
    int xp;
    int n = G[x].size();
    while(cur[x] < n)
    {
        if(!vis[G[x][xp = cur[x]++].second])
        {
            vis[G[x][xp].second] = 1;
            dfs(G[x][xp].first, G[x][xp].second);
        }
    }
    ans[cnt++] = y;
}


bool judge(int n)
{
    int x = 0;
    int y = 0;
    int pos = get_x(0);
    for(int i = 0; i < 62*62+100; i++)
    {
        if(deg[i] > 1 || deg[i] < -1) return false;
        if(deg[i] == 1)
        {
            x++;
            pos = i;
        }
        if(deg[i] == -1) y++;
    }
    if(x != y || x > 1) return false;
    dfs(pos, -1);
    cnt--;
    return cnt >= n;
}

int main()
{
    int n;
    while(cin >>n)
    {
        memset(cur, 0, sizeof(cur));
        memset(vis, 0, sizeof(vis));
        memset(deg, 0, sizeof(deg));
        cnt = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%s", str[i]);
            int x = get_x(i);
            int y = get_y(i);
            G[x].push_back(make_pair(y, i));
            deg[x]++;
            deg[y]--;
        }
        if(!judge(n))
        {
            cout<<"NO"<= 0; i--)
            printf("%s", str[ans[i]]+2);
        puts("");
    }
    return 0;
}


/*
6
abc
bca
cab
cad
adc
dca
*/


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved