2018/1/27

homework

A - The Necklace

题目大意：

一串由彩色珠子连接而成的项链散掉了，掉回地上的珠子判断有没有捡完，并且按顺序排列好（一个珠子两边有颜色，相邻珠子接触部分颜色应相同）。

解题思路：

可以转换为欧拉回路的问题，此处用基本法判断找出欧拉回路，并提前用每个点度数判断是否能构成欧拉回路。

AC代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#define INF 0x3f3f3f3f
#define MAX 1005
using namespace std;
int n,s;
int ka;
typedef pair<int,int> p;
queue<p>ans;
int mp[1005][1005];
int into[1005];
int up;
void dfs(int u)
{
    int f=0;
    for(int i=0;i<1001;i++){
        if(mp[u][i]!=0){
            mp[u][i]--;
            mp[i][u]--;
            dfs(i);
            f = 1;
        }
        if(f == 1){
            ans.push(make_pair(i,u));
            f = 0;
        }
    }
}
void solve()
{
    dfs(s);
    int count1=0;
    stack<p>c;
    while(!ans.empty()){
        p ha,he;
        ha = ans.front();
        ans.pop();
        he.first = ha.second;
        he.second = ha.first;
        c.push(he);
        count1++;
    }
    for(int i=0;i<count1;i++){
        p ha;
        ha = c.top();
        c.pop();
        printf("%d %d\n",ha.first,ha.second);
    }
}
int main()
{
    int t;
    ka = 0;
    scanf("%d",&t);
    while(t--){
        memset(mp,0,sizeof(mp));
        memset(into,0,sizeof(into));
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            if(i == 0)
                s = a;
            mp[a][b]++;
            mp[b][a]++;
            into[a]++;
            into[b]++;
        }
        int flag = 0;
        for(int i=0;i<1001;i++){
            if(into[i]%2 != 0){
                flag = 1;
                break;
            }
        }
        printf("Case #%d\n",++ka);
        if(flag == 1){
            printf("some beads may be lost\n");
        }
        else{
            solve();
        }
        if(t!=0){
            printf("\n");
        }
    }
    return 0;
}

B - Guess

题目大意：

给你一个上三角矩阵，矩阵内有'+','-','0'三种符号，对于X_ij而言，指的是a_i+...+a_j的和大于0时为'+'，小于0时为'-'，等于零时为'0'。你要找出任一原数列。

解题思路：

将其转换为前缀和的形式，即X_ij=sum_j-sum_i-1,将矩阵中每个符号对应的点进行连边，后用拓扑序排列，在枚举出值即可。

Tips

各值的绝对值大小必须小于等于10

AC代码：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#define MAX 105
using namespace std;
struct Edge{
    int next;
    int to;
    int val;
}edge[MAX];
int head[MAX],into[MAX];
int mp[15][15];
int n,cnt;
int B[15];
queue<int>ans;
int ans1[15];
void add(int u,int v,int w)
{
    edge[cnt].to = v;
    edge[cnt].val = w;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}
void topsort()
{
    queue<int>q;
    int count1=0;
    for(int i=0;i<=n;i++){
        if(into[i]==0){
            q.push(i);
            into[i]--;
        }
    }
    while(!q.empty()){
        int s = q.front();
        q.pop();
        ans.push(s);
        count1++;
        for(int i=head[s];i!=-1;i=edge[i].next){
            int cur = edge[i].to;
            if(--into[cur] == 0){
                q.push(cur);
            }
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        cnt=0;
        memset(head,-1,sizeof(head));
        memset(into,0,sizeof(into));
        memset(B,0,sizeof(B));
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j++){
                char c;
                scanf(" %c",&c);
                if(c == '+'){//前n项和关系
                    add(i-1,j,1);
                    into[j]++;
                    mp[i][j]=1;
                    mp[j][i]=1;
                }else if(c == '-'){
                    add(j,i-1,1);
                    into[i-1]++;
                    mp[i][j]=-1;
                    mp[j][i]=-1;
                }else{
                    mp[i][j]=0;
                }
            }
        }
        topsort();
        int c=n;
        while(!ans.empty()){
            ans1[c--]=ans.front();
            ans.pop();
        }
        int pos=0;
        for(int i=1;i<=n;i++){
            if(ans1[i]==0){
                pos=i;
                B[pos]=0;
                break;
            }
        }
        for(int i=pos-1;i>=0;i--){
            int a=ans1[i],b=ans1[i+1];
            if(a>b)
                swap(a,b);
            a++;
            if(!mp[a][b]){
                B[ans1[i]]=B[ans1[i+1]];
            }
            else{
                B[ans1[i]]=B[ans1[i+1]]+1;
            }
        }
        for(int i=pos+1;i<=n;i++){
            int a=ans1[i-1],b=ans1[i];
            if(a>b)
                swap(a,b);
            a++;
            if(!mp[a][b]){
                B[ans1[i]]=B[ans1[i-1]];
            }
            else{
                B[ans1[i]]=B[ans1[i-1]]-1;
            }
        }
        printf("%d",B[1]);
        for(int i=2;i<=n;i++){
            printf(" %d",B[i]-B[i-1]);
        }
        printf("\n");
    }
    return 0;
}