Contest Nowcoder1126 Holiday Team19

发表于 | 更新于 | 分类于 | 评论数：
注：因为是团队赛，所以题并不都是自己写的。

Link

[A]Visiting Cows

After many weeks of hard work, Bessie is finally getting a vacation! After many weeks of hard work, Bessie is finally getting a vacation! numbered 1..N. The cows have set up quite an unusual road network with exactly N-1 roads connecting pairs of cows C1 and C2 (1 <= C1 <= N; 1 <= C2 <= N; C1 != C2) in such a way that there exists a unique path of roads between any two cows.
FJ wants Bessie to come back to the farm soon; thus, he has instructed Bessie that if two cows are directly connected by a road, she may not visit them both. Of course, Bessie would like her vacation to be as long as possible, so she would like to determine the maximum number of cows she can visit. 

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAXN 100005
using namespace std;
int n;
struct qwq {
    int to;
    int nxt;
} e[2*MAXN];
int head[MAXN],cnt;
inline void add(int x,int y) {
    e[++cnt].to=y;
    e[cnt].nxt=head[x];
    head[x]=cnt;
    return ;
}
int dp[MAXN][3];
 
void dfs(int x,int fa) {
    int xuan_max=0,bu_max=0;
    for(int i=head[x]; i; i=e[i].nxt) {
        if(e[i].to==fa)
            continue ;
        dfs(e[i].to,x);
        xuan_max+=dp[e[i].to][0];
        bu_max+=max(dp[e[i].to][0],dp[e[i].to][1]);
    }
    dp[x][0]=bu_max;
    dp[x][1]=xuan_max+1;
    return ;
}
inline int read() {
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9') {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x;
}
 
int main() {
    n=read();
    for(int i=1; i<n; i++) {
        int x=read(),y=read();
        add(x,y),add(y,x);
    }
    dfs(1,-1);
    cout<<max(dp[1][0],dp[1][1]);
    return 0;
}

[B]传球游戏

上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。
游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目。
聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m次以后，又回到小蛮手里。两种传球的方法被视作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有3个同学1号、2号、3号，并假设小蛮为1号，球传了3次回到小蛮手里的方式有1->2->3->1和1->3->2->1，共2种。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 50
using namespace std;
int n,m,dp[MAXN][MAXN];
int main(){
	scanf("%d%d",&n,&m);
	dp[1][0]=1;
	for(int k=1;k<=m;k++){
		dp[1][k]=dp[2][k-1]+dp[n][k-1];
		for(int i=2;i<n;i++)
			dp[i][k]=dp[i-1][k-1]+dp[i+1][k-1];
		dp[n][k]=dp[n-1][k-1]+dp[1][k-1];
	}
	printf("%d",dp[1][m]); return 0;
}

[C]Cow Photographs

Farmer John wants to take a picture of his entire herd of N (1 <= N <= 100,000) cows conveniently numbered 1..N so he can show off to his friends.
On picture day, the cows run to form a single line in some arbitrary order with position i containing cow cic_ici​ (1 <= cic_ici​ <= N). Farmer John has his own ideas about how the cows should line up.
FJ thinks cow i may stand only to the left of cow i+1 (for all i, 1 <= i <= N-1) and that cow N may only stand to the left of Cow 1. Of course, no cow will stand to the left of the first (leftmost) cow in the line.
The cows are hungry for the promised post-photo dinner, so Farmer John wants to take the picture as quickly as possible. Cows are not great at following directions, so he will only choose a pair of adjacent cows and have them switch places once per minute. How quickly is Farmer John able to get them into some acceptable order? 

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
#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
 
const int MAXN=100010;
 
int n,a[MAXN],pos[MAXN],cnt,ans;
 
int tree[MAXN<<1];
 
inline int lowbit(int x){
    return x&(-x);
}
 
int query(int x){
    int ans=0;
    for(;x;x-=lowbit(x))
        ans+=tree[x];
    return ans;
}
 
inline void update(int x,int d){
    for(;x<=n;x+=lowbit(x))
        tree[x]+=d;
}
 
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
        pos[a[i]]=i;
    }
    for(int i=1;i<=n;++i){
        cnt+=i-1-query(a[i]);
        update(a[i],1);
    }
    ans=cnt;
    for(int i=1;i<=n;++i){
        cnt+=n-pos[i]-pos[i]+1;
        ans=min(ans,cnt);
    }
    printf("%lld\n",ans);
    return 0;
}

[D]Chocolate Milk

Farmer John’s milk production and shipping system is an intricate one! He uses milking machines for his many cows to harvest the milk that then flows into pipes.
Each of these pipes connects a milking machine to a joint, where it might be joined by exactly one more pipe (the milk flowing through both pipes merges). The milk then flows through additional pipes (which all start and end at joints) until it reaches the long central pipe connecting to the distribution room.
The milk then goes through a reverse process of splitting at various joints until it is flows into milk tanks that are picked up and taken to market.
Farmer John notices that there is at most one way for milk to travel from one joint to any other joint. Furthermore, since Farmer John is an efficient man by nature, he has made sure that milk will flow through each and every pipe; in other words, no pipe is unneeded.
If we think of a milking machine, joint, or milk tank as a node, there are N (2 <= N <= 100,000) nodes in total (and N-1 pipes connecting them). The input describes each pipe as an ordered pair of nodes, AiA_iAi​ (1 <= AiA_iAi​ <= N) and BiB_iBi​ (1 <= BiB_iBi​ <= N; Ai<BiA_i < B_iAi​<Bi​) indicating milk flows from node AiA_iAi​ to node BiB_iBi​. If there is no pipe coming in to AiA_iAi​, it is a milking machine. Likewise, if no pipe goes out from BiB_iBi​, it is a tank.
The demand of chocolate milk has skyrocketed in recent months, and Farmer John wants to install a chocolate inserter at one of the joints so he can create delicious chocolate milk for customers.
Being thrifty, Farmer John has only bought one chocolate inserter, so he wants to place it at a joint through which all the milk passes. He knows that such a joint exists.
Help Farmer John find all the possible places he can install the chocolate inserter. (Note that Farmer John cannot install the chocolate inserter at the same location as a milking machine.) 

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
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
 
const int MAXN=100010;
const int MAXM=400010;
 
int n;
int Head[MAXN],num,du[MAXN],cnt1,f1[MAXN];
int _Head[MAXN],_num,_du[MAXN],cnt2,f2[MAXN];
 
struct Edge{
    int to,nxt;
}e[MAXN],_e[MAXN];
 
inline void add(int x,int y){
    e[++num].to=y;
    e[num].nxt=Head[x];
    Head[x]=num;
}
inline void _add(int x,int y){
    _e[++_num].to=y;
    _e[_num].nxt=_Head[x];
    _Head[x]=_num;
}
 
int dfs1(int x){
    if(f1[x]) return f1[x];
    int sum=0;
    if(du[x]==0) ++sum;
    for(int i=Head[x];i;i=e[i].nxt){
        int to=e[i].to;
        sum+=dfs1(to);
    }
    return f1[x]=sum;
}
 
int dfs2(int x){
    if(f2[x]) return f2[x];
    int sum=0;
    if(_du[x]==0) ++sum;
    for(int i=_Head[x];i;i=_e[i].nxt){
        int to=_e[i].to;
        sum+=dfs2(to);
    }
    return f2[x]=sum;
}
 
int main()
{
    scanf("%d",&n);
    int x,y;
    for(int i=1;i<n;++i){
        scanf("%d%d",&x,&y);
        add(x,y); ++du[x];
        _add(y,x); ++_du[y];
    }
    for(int i=1;i<=n;++i){
        if(du[i]==0) ++cnt1;
        if(_du[i]==0) ++cnt2;
    }
    for(int i=1;i<=n;++i)
        if(!f1[i]) dfs1(i);
    for(int i=1;i<=n;++i)
        if(!f2[i]) dfs2(i);
    for(int i=1;i<=n;++i)
        if(_du[i]!=0&&f1[i]==cnt1&&f2[i]==cnt2)
            printf("%d\n",i);
    return 0;
}

[E]Math Practice

One lovely afternoon, Bessie’s friend Heidi was helping Bessie review for her upcoming math exam.
Heidi presents two integers A (0 <= A <= 45) and B (1 <= B <= 9) to Bessie who must respond with an integer E in the range 1..62. E is the smallest integer in that range that is strictly greater than A and also has B as the first digit of 2 raised to the E-th power. If there is no answer, Bessie responds with 0.
Help Bessie correctly answer all of Heidi’s questions by calculating her responses.

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int E[64]={1,2,4,8,1,3,6,1,2,5,1,2,4,8,1,3,6,1,2,5,1,2,4,8,1,3,6,1,2,5,1,2,4,8,1,3,6,1,2,5,1,2,4,8,1,3,7,1,2,5,1,2,4,9,1,3,7,1,2,5,1,2,4,9};
inline int read() {
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9') {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x;
}
int main() {
    int a=read(),b=read();
    for(int i=a+1;i<=62;i++)
        if(b==E[i]){
            cout<<i<<endl;
            return 0;
        }
    cout<<"0";
    return 0;
}

[F]立体图

小渊是个聪明的孩子，他经常会给周围的小朋友们讲些自己认为有趣的内容。最近，他准备给小朋友们讲解立体图，请你帮他画出立体图。
小渊有一块面积为mn的矩形区域，上面有mn个边长为1的格子，每个格子上堆了一些同样大小的吉姆（积木的长宽高都是1），小渊想请你打印出这些格子的立体图。我们定义每个积木为如下格式，并且不会做任何翻转旋转，只会严格以这一种形式摆放：

img

每个顶点用1个加号’+’表示，长用3个”-“表示，宽用1个”/”表示，高用两个”|”表示。字符’+’，‘-‘，’/’，‘|’的ASCII码分别为43，45，47，124。字符’.’（ASCII码46）需要作为背景输出，即立体图里的空白部分需要用’.’代替。立体图的画法如下面的规则：

若两块积木左右相邻 若两块积木上下相邻 若两块积木前后相邻

img img img

立体图中，定义位于第(m,1)的格子（即第m行第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
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstdlib>
using std::max;
const int maxn=51;
int data[maxn][maxn];
char m[maxn*5][maxn*5];
int f[maxn][maxn];
int L=0,W=0;
void clear(int x,int y,int len)
{
    for(int i=0;i<len;i++)
        m[x][y+i]=' ';
    return ;
}
void out()
{
    for(int i=L;i>=1;i--)
    {
        for(int j=1;j<=W;j++)
            putchar(m[i][j]);
        putchar('\n');
    }
    //printf("------------------------\n");
    return ;
}
void insert(int x,int y)
{
    for(int i=0;i<=3;i++)   clear(x+i,y,5);
    clear(x+4,y+1,5);clear(x+5,y+2,5);
    m[x+2][y+5]=m[x+3][y+5]=' ';
    for(int i=1;i<=3;i++)
        m[x][y+i]=m[x+3][y+i]=m[x+5][y+2+i]='-';
    for(int i=1;i<=2;i++)
        m[x+i][y]=m[x+i][y+4]=m[x+i+2][y+6]='|';
    m[x+4][y+1]=m[x+4][y+5]=m[x+1][y+5]='/';
    m[x][y]=m[x+3][y]=m[x+5][y+2]=m[x+5][y+6]=m[x+3][y+4]=m[x+2][y+6]=m[x][y+4]='+';
    W=max(W,y+6);
    L=max(L,x+5);
}
void init()
{
    for(int i=1;i<maxn*5;i++)
        for(int j=1;j<maxn*5;j++)
            m[i][j]='.';
    return ;
}
int main()
{
    init();
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=n;i>=1;i--)
        for(int j=1;j<=m;j++)
            scanf("%d",&f[i][j]);
    bool F=true;
    int cnt=0;
    while(F)
    {
        F=false;
        cnt++;
        for(int i=n;i>=1;i--)
            for(int j=1;j<=m;j++)
                if(f[i][j])
                {
                    int x=3*cnt-4+i*2;
                    int y=4*j-5+i*2;
                    f[i][j]--;
                    if(f[i][j]) F=true;
                    insert(x,y);
                    //out();
                }
    }
    out();
    return 0;
}

[G]Candy

Farmer John knows that Bessie loves to eat candy. FJ has N (1 <= N <= 40,000) candies that he wants to give Bessie over some number of days. Each day, Farmer John gives Bessie a choice of how many candies she chooses to eat that day by choosing the number from a master list FJ supplies that has Nopt (1 <= Nopt <= 50) different options, CiC_iCi (1 <= CiC_iCi <= N). She must take exactly CiC_iCi candies, no more, no less.
Farmer John has also disclosed F (1 <= F <= 50) of his favorite numbers, FNiFN_iFNi​ (1 <= FNiFN_iFNi​ <= N). Whenever the number of candies remaining at the end of the day precisely matches one of these favorite numbers, Bessie has the option to have him add exactly M (1 <= M <= 100) more candies to the candy supply. Bessie might get another option to add M candies several times if adding candies creates another favorite number. In the best circumstances, Bessie can obtain an infinite amount of candy!
When Bessie cannot choose some amount of candy to take (because there is not enough), and the number of candies remaining is not any of FJ’s favorite numbers, she cannot have any more candy.
Unfortunately, Bessie cannot think ahead as far as she’d like to, so she needs your help in order to eat as many candies as possible. 

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>

using std::max;
using std::queue;

const int maxn=101000;

int ind[maxn],like[maxn];
int ate[maxn],f[maxn];
int g[maxn];
int n,nopt,fn,m;
int vis[maxn],instk[maxn];
queue<int>q;

template<class T>
void read(T& val)
{
    char c=getchar(); val=0;
    while(!isdigit(c)) c=getchar();
    while(isdigit(c))
    {
        val=(val<<3)+(val<<1)+c-'0';
        c=getchar();
    }
    return ;
}

void dfs(int now)
{
    vis[now]=instk[now]=1;
    int nxt;
    for(int i=1;i<=nopt;++i)
    {
        nxt=now-ate[i];
        if(nxt<0) continue;
        if(instk[nxt])
        {
            printf("-1");
            exit(0);
        }
        else
        {
            ++ind[nxt];
            if(!vis[nxt]) dfs(nxt);
        }
    }
    if(like[now]&&now!=n)
    {
        nxt=now+m;
        if(instk[nxt])
        {
            printf("-1");
            exit(0);
        }
        else
        {
            ++ind[nxt];
            if(!vis[nxt]) dfs(nxt);
        }
    }
    instk[now]=0;
}

int main()
{
    // freopen("data.in","r",stdin);
    read(n),read(nopt),read(fn),read(m);
    for(int i=1;i<=nopt;++i) read(ate[i]);
    for(int i=1;i<=fn;++i) read(f[i]),like[f[i]]=1;
    dfs(n);
    /*
     * for(int i=0;i<=n+m;++i) if(vis[i])
     *     for(int j=1;j<=nopt;++j) if(i-ate[j]>=0&&vis[i-ate[j]])
     *         ++ind[i-ate[j]];
     * for(int i=1;i<=fn;++i) if(vis[f[i]]&&vis[f[i]+m]&&f[i]!=n)
     *     ++ind[f[i]+m];
     */
    q.push(n); ind[n]=0;
    int pas,nxt;
    while(!q.empty())
    {
        pas=q.front(); q.pop();
        for(int i=1;i<=nopt;++i)
        {
            nxt=pas-ate[i];
            if(nxt<0) continue;
            g[nxt]=max(g[nxt],g[pas]+ate[i]);
            --ind[nxt];
            if(!ind[nxt]) q.push(nxt);
        }
        if(like[pas]&&pas!=n)
        {
            nxt=pas+m;
            g[nxt]=max(g[nxt],g[pas]);
            --ind[nxt];
            if(!ind[nxt]) q.push(nxt);
        }
    }
    int ans=0;
    for(int i=0;i<=n+m;++i) ans=max(ans,g[i]);
    printf("%d",ans);
    return 0;
}

[H]Banner

Bessie is returning from a long trip abroad, and Farmer John wants to erect a nice ‘Welcome Home’ banner in her pasture for her arrival. The banner will hang between two poles on a wire whose length is in the range L1..L2 (1 <= L1 <= L2; L1 <= L2 <= 1,500).
The pasture’s size is W x H (1 <= W <= 1,000; 1 <= H <= 1,000), and Farmer John has installed a post at every point with integer
coordinates. Of these (W + 1) * (H + 1) points, Farmer John must pick just two that will hold either end of the wire from which he will hang the banner.
FJ wants no interference with his banner as it hangs and requires that no post be directly under the tight wire he stretches between the two chosen posts.
Farmer John needs your help to figure out how many possible ways he can hang the banner. He knows the number is large and that a 32-bit integer might not be sufficient to compute the answer. 

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
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
 
int L1,L2,W,H,ans;
 
inline int gcd(int a,int b){
    if(!b) return a;
    return gcd(b,a%b);
}
 
signed main()
{
    scanf("%lld%lld%lld%lld",&W,&H,&L1,&L2);
    for(int i=0;i<=W;++i)
        for(int j=0;j<=H;++j){
            double len=sqrt(i*i+j*j);
            if(gcd(i,j)==1&&L1<=len&&len<=L2){
                if(i==0||j==0) ans+=(W-i+1)*(H-j+1);
                else ans+=(W-i+1)*(H-j+1)*2;
            }
        }
    printf("%lld\n",ans);
    return 0;
}

[I]Race Results

The herd has run its first marathon! The N (1 <= N <= 5,000) times have been posted in the form of Hours (0 <= Hours <= 99), Minutes (0 <= Minutes <= 59), and Seconds (0 <= Seconds <= 59). Bessie must sort them (by Hours, Minutes, and Seconds) into ascending order, smallest times first. 

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
#include <iostream>
#include <cstdio>
#include <cstdio>
#include <algorithm>

using namespace std ;

typedef long long LL ;
const int MAXN = 100010 ;
const int MAXM = 100010 ;
const int INF = 0x7fffffff ;
int N ;
struct TIME {
	int X, Y, Z ;
}	E[MAXN << 1] ;

inline int Read() {
	int X = 0, F = 1 ; char ch = getchar() ;
	while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
	while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
	return X * F ;
}

inline bool CMP(TIME A, TIME B) {
	if (A.X == B.X) {
		if (A.Y == B.Y)
			return A.Z < B.Z ;
		return A.Y < B.Y ;
	}
	return A.X < B.X ;
}

int main() {
	N = Read() ;
	for (int i =  1 ; i <= N ; i ++) {
		E[i].X = Read() ;
		E[i].Y = Read() ; 
		E[i].Z = Read() ;
	}
	sort(E + 1, E + N + 1, CMP) ;
	for (int i = 1 ; i <= N ; i ++)
		printf("%d %d %d\n", E[i].X , E[i].Y , E[i].Z) ;
	return 0 ;
}

[J]Buying Feed

Farmer John needs to travel to town to pick up K (1 <= K <= 10,000) pounds of feed. Driving a mile with K pounds of feed costs FJ KK cents; driving D miles with K pounds of feed in his truck costs FJ DK*K cents.
FJ can purchase feed from any of N (1 <= N <= 500) stores (conveniently numbered 1..N) that sell feed. Each store is located on a segment of the X axis whose length is E (1 <= E <= 500) miles. Store i is at location XiX_iXi​ (0 < XiX_iXi​ < E) on the number line and can sell FJ as much as FiF_iFi​ (1 <= FiF_iFi​ <= 10,000) pounds of feed at a cost of CiC_iCi​ (1 <= CiC_iCi​ <= 10,000,000) cents per pound. Surprisingly, a given point on the X axis might have more than one store.
FJ starts driving at location 0 on this number line and can drive only in the positive direction, ultimately arriving at location E with at least K pounds of feed. He can stop at any of the feed stores along the way and buy any amount of feed up to the the store’s limit.
What is the minimum amount FJ must pay to buy and transport the K pounds of feed? FJ knows he can purchase enough feed. 

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
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
using namespace std;
 
const int N=10010;
 
int n,E,K,dp[N];
struct Data{
    int x,f,c;
} a[N];
 
inline bool cmp(Data p,Data q){
    return p.x<q.x;
}
 
signed main()
{
    scanf("%lld%lld%lld",&K,&E,&n);
    for(int i=1;i<=n;++i)
        scanf("%lld%lld%lld",&a[i].x,&a[i].f,&a[i].c);
    sort(a+1,a+1+n,cmp);
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;++i){
        int sum=0;
        for(int k=1;sum+k<=a[i].f;k<<=1){
            sum+=k;
            for(int j=K;j>=k;--j)
                dp[j]=min(dp[j],dp[j-k]+a[i].c*k+(j*j-(j-k)*(j-k))*(E-a[i].x));
        }
        int k=a[i].f-sum;
        for(int j=K;j>=k;--j)
            dp[j]=min(dp[j],dp[j-k]+a[i].c*k+(j*j-(j-k)*(j-k))*(E-a[i].x));
    }
    printf("%lld\n",dp[K]);
    return 0;
}

[K]排座椅

上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i，j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。
请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std; 
int m,n,k,l,d;//变量名最好起与题目一致的 
int x[1005],y[1005];//横纵坐标数组 
int c[1005],o[1005];//桶排要用的数组
int main() {
    scanf("%d%d%d%d%d",&m,&n,&k,&l,&d); 
    for(int i=1;i<=d;i++) { 
        int xi,yi,pi,qi; 
        scanf("%d%d%d%d",&xi,&yi,&pi,&qi); 
        if(xi==pi) 
            x[min(yi,qi)]++;//表示隔开这两排的价值 
        else 
            y[min(xi,pi)]++; //记得取min，即过道与前一个坐标保持一致 
    } 
    for(int i=1;i<=k;i++){//开始桶排 
        int maxn=-1;//为了求出每次的最大值，需要每次扫一遍 
        int p; 
        for(int j=1;j<m;j++){ 
            if(y[j]>maxn){ 
                maxn=y[j]; 
                p=j; 
            } 
        } 
        y[p]=0;//求出max之后一定要记得清零！！否则无论排多少次都是一个答案 
        c[p]++;//桶排不解释 
    } 
    for(int i=1;i<=l;i++){ 
        int maxn=-1; 
        int p; 
        for(int j=1;j<n;j++){ 
            if(x[j]>maxn){ 
                maxn=x[j]; 
                p=j; 
            } 
        } 
        x[p]=0; //同上 
        o[p]++; 
    } 
    for(int i=0;i<1005;i++)//输出答案 
    { 
        if(c[i])//表示需要隔开这行 
            printf("%d ",i); 
    } 
    printf("\n"); 
    for(int i=0;i<1005;i++) 
    { 
        if(o[i]) 
            printf("%d ",i); //同上 
    } 
    return 0; 
}

[L] Daisy Chains in the Field

Farmer John let his N (1 <= N <= 250) cows conveniently numbered 1..N play in the field. The cows decided to connect with each other using cow-ropes, creating M (1 <= M <= N*(N-1)/2) pairwise connections. Of course, no two cows had more than one rope directly connecting them. The input shows pairs of cows c1 and c2 that are connected (1 <= c1 <= N; 1 <= c2 <= N; c1 != c2).
FJ instructed the cows to be part of a chain which contained cow #1. Help FJ find any misbehaving cows by determining, in ascending order, the numbers of the cows not connected by one or more ropes to cow 1 (cow 1 is always connected to herself, of course). If there are no misbehaving cows, output 0. 

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define MAXN 255
using namespace std;
int n;
struct qwq{
    int to;
    int nxt;
}e[MAXN*MAXN*2];
int head[MAXN],cnt;
void add(int x,int y){
    e[++cnt].to=y;
    e[cnt].nxt=head[x];
    head[x]=cnt;
    return ;
}
inline int read() {
    int x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9') {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x;
}
bool vis[MAXN];
void dfs(int x,int fa){
    vis[x]=1;
    for(int i=head[x];i;i=e[i].nxt){
        if(vis[e[i].to])
            continue ;
        dfs(e[i].to,x);
    }
    return ;
}
int main() {
    int n=read(),m=read();
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        add(x,y),add(y,x);
    }
     
    dfs(1,-1);
    int bb=0;
    for(int i=1;i<=n;i++)
        if(!vis[i]){
            cout<<i<<endl;
            bb=1;
        }
    if(bb==0)
        cout<<"0";
    return 0;
}

本文标题:Contest Nowcoder1126 Holiday Team19

文章作者:Sue Shallow

发布时间:2019年10月21日 - 23:55:00

最后更新:2019年11月11日 - 19:52:55

原始链接:http://Yeasion.github.io/2019/10/21/Contest Nowcoder1126 Holiday Team19/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。