[原创]2014上海全国邀请赛 【(5+3)/10】

2017-07-23 20:46:34 Tabris_ 阅读数：422

博客爬取于2020-06-14 22:39:32
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/75948179

日常血崩。
菜到爆了.

A HDU 5090 Game with Pearls

——————————————————————————————————————————
给你一个序列，可以把每个元素加上k的倍数或者不加， 问你最后能不能组成一个序列，第1个元素是1，第2个元素是2，第3个元素是3，。。

暴力模拟就行，从大小1的数开始，留下本身需要的1个，剩下的不断加K，知道当前的数没出现过。

最后扫一下判断就行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

const int N = 1e5+7;

/******************************************************/

int a[N];
int vis[N];
int n,k;
int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        memset(vis,0,sizeof(vis));
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            vis[a[i]]++;
        }
        int flag = 1;
        for(int i=1;i<=n;i++){
            for(int j=1;vis[i]>1;j++){
                if(vis[j*k+i] == 0){
                    vis[j*k+i] = 1;
                    vis[i]--;
                }
            }
        }

        for(int i=1;i<=n;i++){
            if(vis[i]!=1){
                flag=0;
                break;
            }
        }

        if(flag) puts("Jerry");
        else     puts("Tom");
    }
    return 0;
}

B HDU 5091 Beam Cannon

——————————————————————————————————————————
在二维坐标系上给你一堆点,然后问你w*h这么大的矩形,最多能包含多少个点

用到了扫描线;

首先考虑一维的情况
如果是一维的,要统计长为w的线段最多能包括多少个位置怎么搞?

可以反过来考虑,然后变成一堆长w的线段覆盖,然后求的就是那个被覆盖最多的点,区间更新后求最大值就行了

而这个题
可以考虑将一个点变成一个矩形,
然后从左向右扫描

使扫描过程中,遇到矩形的左边就+1,右边就-1,

并维护一个线段树区间更新取最大值就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N   = 1e6+7;
const int MOD = 1e9+7;

# define mp make_pair
# define pb push_back
# define yy1 second.first
# define yy2 second.second
# define vv  first.second
/*********************************************/

vector<pair<pair<int,int>,pair<int,int> > >line;


int mx[N<<2],lazy[N<<2];

void pushdown(int rt){
    if(lazy[rt]){
        lazy[rt<<1  ]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        mx[rt<<1  ]+=lazy[rt];
        mx[rt<<1|1]+=lazy[rt];
        lazy[rt]=0;
    }
}

void pushup(int rt){
    mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
}

void update(int rt,int l,int r,int L,int R,int v){
    if(L<=l&&r<=R){
        lazy[rt]+=v;
        mx[rt]+=v;
        return ;
    }
    int m = r+l >> 1;
    pushdown(rt);
    if(L<=m) update(rt<<1  ,l  ,m,L,R,v);
    if(R> m) update(rt<<1|1,m+1,r,L,R,v);
    pushup(rt);
}

int query(int rt,int l,int r,int L,int R){

}
int n,w,h;
int main(){
    int _ = 1;
    for(;scanf("%d",&n);){
        if(n==-1) break;
        scanf("%d%d",&w,&h);

        memset(mx,0,sizeof(mx));
        memset(lazy,0,sizeof(lazy));
        line.clear();
        for(int i=1,x,y;i<=n;i++){
            scanf("%d%d",&x,&y);
            line.pb(mp(mp(x  , 1),mp(y,y+h)));
            line.pb(mp(mp(x+w, 2),mp(y,y+h)));
        }

        sort(line.begin(),line.end());

        int X = 90000;
        int ans = 0;
        for(int i=0;i<line.size();i++){
            if(line[i].vv == 1){
                update(1,1,X,line[i].yy1+20001,line[i].yy2+20001, 1);
                ans = max(ans,mx[1]);
            }
            else {
                ans = max(ans,mx[1]);
                update(1,1,X,line[i].yy1+20001,line[i].yy2+20001,-1);
            }

        }
        printf("%d\n",ans);
    }
    return 0;
}

C HDU 5092 Seam Carving

——————————————————————————————————————————
给你一个矩阵,让你找一个从上到下的路线,使得这个路线经过数的和最小,并且尽量靠右.

注意 a[i][j] 只能走到 a[i+1][j-1],a[i+1][j],a[i+1][j+1]

所以我们知道dp下到每个点的最小和，然后在最后一行找到最后一个最小的位置不算向回找就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N   = 1e6+7;
const int MOD = 1e9+7;

/*********************************************/

LL dp[111][111],a[111][111];
int ms[111],len,n,m;
int main(){
    int _ = 1,kcase = 0;
    for(scanf("%d",&_);_--;){
        scanf("%d%d",&n,&m);

        len = 0;
        memset(dp,0,sizeof(dp));

        for(int i=1;i<=n;i++){
             a[i][0]= a[i][m+1]=10000000000000ll;
            dp[i][0]=dp[i][m+1]=10000000000000ll;
            for(int j=1;j<=m;j++)
                scanf("%lld",&a[i][j]);
        }

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                dp[i][j]=a[i][j]+
                min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1]));
            }
        }

        int p,mi = 10000000000000ll;;
        for(int i=1;i<=m;i++){
            if(dp[n][i]<=mi){
                mi = dp[n][i];
                p  = i;
            }
        }

        ms[++len] = p;
        int tp;
        for(int i=n-1;i;i--){
            mi = dp[i][p-1];
            tp = p-1;
            if(mi>=dp[i][p]){
                mi = dp[i][p];
                tp = p;
            }
            if(mi>=dp[i][p+1]){
                mi = dp[i][p+1];
                tp = p+1;
            }
            p=tp;
            ms[++len]=p;
        }

        printf("Case %d\n",++kcase);
        for(int i=len;i;i--)
            printf("%d%c",ms[i],(i==1)?'\n':' ');
    }
    return 0;
}

D HDU 5093 Battle ships

——————————————————————————————————————————
给你一个NM的图,其中’‘可以放传,但是注意同一行一列只能放一个船,除非被’#'隔开,问你最多能放几个船.

首先考虑每个行和列分开之后,没有被隔开的部分就是一个整体了,

然后考虑 ,处理完的这一个个, 行与列没有被隔开的中

假设行1 和列1,列2,列3, 没有被隔开,

那么行1只能找一个列对应的位置来放船，

然后这就是一个二分匹配模型了，、、

然后就用行与列建二分图求最大匹配就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
# include<stdio.h>
# include<string.h>
# include<vector>
using namespace std;
vector<int>mp[25000+50];
int vis[25000+50];
int match[25000+50];
int find(int u){
  //  printf("%d %d\n",u,mp[u].size());
    for(int i=0;i<mp[u].size();i++){
        int v=mp[u][i];
        if(vis[v]==0){
            vis[v]=1;
            if(match[v]==-1||find(match[v])){
                match[v]=u;
                return 1;
            }
        }
    }
    return 0;
}

int h[111][111],l[111][111];
char a[111][111];

int n,m;

void add(int u,int v){
  //  printf("%d %d< -\n",u,v);
    mp[u].push_back(v);
}

void solve(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",a[i]+1);

    int cnt = 0;
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
        h[i][j]=l[i][j]=-1;

    memset(h,-1,sizeof(h));
    memset(l,-1,sizeof(l));

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]=='#') continue;
            if(-1==h[i][j-1])h[i][j]=++cnt;
            else h[i][j]=h[i][j-1];
        }
    }

    for(int j=1;j<=m;j++){
        for(int i=1;i<=n;i++){
            if(a[i][j]=='#') continue;
            if(-1==l[i-1][j])l[i][j]=++cnt;
            else l[i][j]=l[i-1][j];
        }
    }

    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
        if(a[i][j]=='*') add(h[i][j],l[i][j]);

    for(int i=1;i<=cnt;i++) match[i]=-1;

    int output=0;
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=cnt;j++) vis[j]=0;
        if(find(i))output++;
    }

    printf("%d\n",output);
    for(int i=1;i<=cnt;i++) mp[i].clear();
    return ;
}

int main(){
    int t;for(scanf("%d",&t);t--;) solve();
}

E HDU 5094 Maze

——————————————————————————————————————————
给你一个图，

二进制枚举状态搜索，

队友A的,待补

-----------------------Update-----------------------------

就是搜索么。
我用a[x][y][0~3] 记录每个位置4个方向的们需要那种钥匙开 用a[x][y][4]记录(x,y)这个位置的钥匙是那种，

因为又9种钥匙， 所以只要用一个9位的二进制数进行枚举就好了

用vis[x][y][1<<10] 来标记每种状态下走到(x,y)、、

然后直接搜索就好了

注意不能走到输出-1；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
# include <bits/stdc++.h>

typedef long long int LL;
using namespace std;

# define abs(x) ((x)>0?(x):-(x))
# define rep(a,b,c) for(int a=(b),end=(c);a<=end;a++)

const int N   = 2000+7;
const int MOD = 1e9+7;

/******************************************************/

int n,m,q,k;
int a[55][55][10];
bool vis[55][55][1<<11];
int fx[]={0,0,1,-1};
int fy[]={1,-1,0,0};

struct node {
    int x,y,step,s;
};

int bfs(int x,int y){
    queue<node>q;
    node tmp,tem;
    tmp.x    = x,tmp.y = y;
    tmp.step = 0,tmp.s = 0;
    q.push(tmp);
    vis[1][1][0]=1;
    int xx,yy,ss,st;
    while(!q.empty()){
        tem = q.front();q.pop();
        if(tem.x == n&&tem.y == m)
            return tem.step;

        for(int i=0;i<4;i++){
            if( a[tem.x][tem.y][i]==-1) continue;
            if((a[tem.x][tem.y][i]&tem.s) != a[tem.x][tem.y][i]) continue;
            xx = tem.x + fx[i];
            yy = tem.y + fy[i];
            ss = (tem.s | a[xx][yy][4]);
            st = tem.step + 1;
            if(xx<1||xx>n) continue;
            if(yy<1||yy>m) continue;
            if(vis[xx][yy][ss]) continue;
            vis[xx][yy][ss]=1;
            tmp.x    = xx;
            tmp.y    = yy;
            tmp.s    = ss;
            tmp.step = st;
            q.push(tmp);
        }
    }
    return -1;
}


int main(){
    while(~scanf("%d%d%d",&n,&m,&q)){
        memset(vis,0,sizeof(vis));
        memset(a  ,0,sizeof(a  ));

        scanf("%d",&k);
        for(int i=1,f,x1,x2,y1,y2,p;i<=k;i++){
            scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&p);
            if(p == 0) f=-1;
            else       f=1<<(p-1);
            for(int j=0;j<4;j++){
                if(x1+fx[j]==x2&&y1+fy[j]==y2){
                    a[x1][y1][j]|=f;
                    break;
                }
            }
            for(int j=0;j<4;j++){
                if(x2+fx[j]==x1&&y2+fy[j]==y1){
                    a[x2][y2][j]|=f;
                    break;
                }
            }
        }

        scanf("%d",&k);
        for(int i=1,x1,y1,p;i<=k;i++){
            scanf("%d%d%d",&x1,&y1,&p);
            a[x1][y1][4]|=1<<(p-1);
        }

        printf("%d\n",bfs(1,1));
    }
    return 0;
}

F HDU 5095 Linearization of the kernel functions in SVM

——————————————————————————————————————————
给你10个系数,让你把10项的多项式的最简形式表示出来,

小模拟

注意开始的数是正数的时候没有正号,
系数为1 的要省略

–

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

const int N = 1e5+7;

/******************************************************/

int a[N];
char ch[100]={' ','p','q','r','u','v','w','x','y','z'};
int n,k;
int main(){
    int _; scanf("%d",&_);
    while(_--){
        for(int i=1;i<=10;i++) scanf("%d",&a[i]);

        int i;
        for(i=1;i<=10;i++) if(a[i]!=0) break;

        int flag=0;

        for(;i<10;i++){
            if(a[i]==0) continue;
            if(a[i]<0) {flag=1;
                if(a[i]==-1) printf("-%c",ch[i]);
                else         printf("%d%c",a[i],ch[i]);
            }
            else {
                if(flag) printf("+");flag=1;
                if(a[i]!=1) printf("%d%c",a[i],ch[i]);
                else        printf("%c",ch[i]);
            }
        }

        if(a[10]!=0) {
            if(a[10]>0) {
                if(flag) printf("+");flag=1;
                printf("%d",a[10]);
            }
            else {
                printf("%d",a[10]),flag=1;
            }
        }
        if(flag == 0) printf("0");
        puts("");

    }
    return 0;
}
/***
5555
0 0 0 0 0 0 0 0 0 0
-5 -2  5 5 5 5 5 5 5 5
0 46 3 4 -5 -22 -8 -32 24 27
2 31 -5 0 0 12 0 0 -49 12
-1 -1 -1 0 0 4 0 0 -6 7
0 0 0 0 0 -5 0 0 0 0
1 1 1 1 1 1 1 1 1 1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 1 -1 1 -1 1 -1 1 -1 1
1 -1 1 -1 1 -1 1 -1 1 -1

*/

G HDU 5096 ACM Rank

——————————————————————————————————————————

大模拟,不补.

–

H HDU 5097 Page Rank

——————————————————————————————————————————
待补…

I HDU 5098 Smart Software Installer

——————————————————————————————————————————
给你一堆程序,后面带’*‘好的需要重启之后才能生效,’:’ 后面的是需要安装完这个程序，才能开始安装的程序

问你最少需要打印多少次

题目很水，就是题面太长了。没读。。。

只要注意到要把当前需要重启的程序个数最大化就好了。

过程就是个拓扑，

然后就是如何处理这个恶心的读入了。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N   = 1e6+7;
const int MOD = 1e9+7;

# define pb push_back

/*********************************************/

int deg[N];
bool vis[N];
int cnt;
int ms[N],len;
int ms2[N],len2;

string s;char t[N];
vector<int >G[N];

void add(int u,int v){
    G[u].pb(v);
    deg[v]++;
}

map<string ,int >mp;

void topo(){
    queue<int >q;
    while(len) q.push(ms[len--]);

    while(!q.empty()){// puts("++");
        int u = q.front();q.pop();
//        printf("cnt = %d  : %d\n",cnt,u);
        for(int i=0;i<G[u].size();i++){
            int to = G[u][i];
            deg[to]--;
            if(deg[to] == 0){
                if(vis[to]) ms[++len] = to;
                else q.push(to);//,printf("%d <--\n",to);
            }
        }
    }
}

void solve(){
    len = len2 = 0;

    for(int i=1;i<=cnt;i++)
        if(deg[i]==0){
            if(vis[i]) ms2[++len2]=i;
            else        ms[++len ]=i;
        }
//    printf("<%d,%d>\n",len,len2);
    int ans = 0;
    for(;len||len2;){ans++;
        topo();
        while(len2) ms[++len] = ms2[len2--];
    }
    printf("%d\n",ans-1);

    for(int i=1;i<=cnt;i++) G[i].clear(),vis[i]=deg[i]=0;
    return ;
}

void init(){
    mp.clear();cnt=0;

    int flag;
    string id1,id2;
    while(getline(cin,s) != NULL){
         if(s[0] == '\0') break;
         istringstream sin(s);
         sin >> t;
         flag = 0;
         int len = strlen(t);
         for(int i = 0; i < len; ++i)
             if(t[i] == '*') flag = 1;
         t[len - 1 - flag] = '\0';
         id1 = t;
         if(mp[id1] == 0) mp[id1]= ++cnt;
         vis[mp[id1]] = flag;
         while(sin >> id2){
             if(mp[id2] == 0)
                 mp[id2] = ++cnt;
             add(mp[id2],mp[id1]);
         }
    }

    return ;
}

int main(){
    int _ = 1,kcase = 0;
    cin>>_;
    getchar();
    getchar();
    for(;_--;){
        init();
//        for(int i=1;i<=cnt;i++){
//            printf("%d: ",i);
//            for(int j=0;j<G[i].size();j++){
//                printf(" %d-%d*",G[i][j],deg[G[i][j]]);
//            }
//            puts("");
//        }
//        for(int i=1;i<=cnt;i++) printf("deg[%d]=%d\n",i,deg[i]);

        printf("Case %d: ",++kcase);
        solve();
    }
    return 0;
}

J HDU 5099 Comparison of Android versions

——————————————————————————————————————————

给你两个字符串,然后按照规则比较下大小.

我做傻逼了

队友A的

题傻逼不补

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
# include <bits/stdc++.h>
using namespace std;
char a[1500];
char b[1500];
# define mme(i,j) memset(i,j,sizeof(i))
void print(int vala ,int valb )
{
    if(vala>valb)printf(">");
    else if(vala==valb)printf("=");
    else printf("<");
}

int opt[3];
int main()
{
    int t;
    int kase=0;
    scanf("%d",&t);
    while(t--)
    {
        mme(opt,0);
        scanf("%s%s",a+1,b+1);
        printf("Case %d: ",++kase);
        if(a[1]==b[1])//0--->=   1---->  -1----<
            opt[1]=0;
        else if(a[1]>b[1])
            opt[1]=1;
        else opt[1]=-1;

        if(a[2]!=b[2])// bu tong
        {
            if(a[3]==b[3])
            {
                if(a[4]==b[4])
                {
                    if(a[5]==b[5])
                        opt[2]=0;
                    else{
                        if(a[5]>b[5])
                            opt[2]=1;
                        else
                            opt[2]=-1;
                    }
                }else {
                    if(a[4]>b[4])
                        opt[2]=1;
                    else opt[2]=-1;
                }
            }else {
                if(a[3]>b[3])
                    opt[2]=1;
                else
                    opt[2]=-1;
            }
        }else {
            if(strcmp(a+3,b+3)>0)
                opt[2]=1;
            else if(strcmp(a+3,b+3)<0)
                opt[2]=-1;
            else opt[2]=0;
        }
        if(opt[1]==1)
            printf("> ");
        else if(opt[1]==-1)
            printf("< ");
        else printf("= ");

        if(opt[2]==1)
            printf(">\n");
        else if(opt[2]==-1)
            printf("<\n");
        else printf("=\n");
    }
}