AtCoder Beginner Contest 133_综合

	Task Name	Time Limit	Memory Limit
A	T or T	2 sec	1024 MB	Submit
B	Good Distance	2 sec	1024 MB	Submit
C	Remainder Minimization 2019	2 sec	1024 MB	Submit
D	Rain Flows into Dams	2 sec	1024 MB	Submit
E	Virus Tree 2	2 sec	1024 MB	Submit
F	Colorful Tree	4 sec	1024 MB	Submit

A 水题

B 水题（读错题意了，但读懂了就是水题）

C - Remainder Minimization 2019

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 300300 points

Problem Statement

You are given two non-negative integers LL and RR. We will choose two integers ii and jj such that L≤i<j≤RL≤i<j≤R. Find the minimum possible value of (i×j) mod 2019(i×j) mod 2019.

Constraints

All values in input are integers.
0≤L<R≤2×1090≤L<R≤2×109

Input

Input is given from Standard Input in the following format:

LL RR

Output

Print the minimum possible value of (i×j) mod 2019(i×j) mod 2019 when ii and jj are chosen under the given condition.

Sample Input 1 Copy

Copy

2020 2040

Sample Output 1 Copy

Copy

When (i,j)=(2020,2021)(i,j)=(2020,2021), (i×j) mod 2019=2(i×j) mod 2019=2.

Sample Input 2 Copy

Copy

4 5

Sample Output 2 Copy

Copy

We have only one choice: (i,j)=(4,5)(i,j)=(4,5).

题意：

给你L，R，求【L，R】之间的两个数i和j，使得I*j%2019最小。

分析：

这题被long long 卡死了，尽然i，j也需要long long。

我们知道里面只要有2019的倍数，则最小就是0

加一个特判：

int x1=l/2019; 求出l前面的可以整除2019的数，不包括l
int y1=r/2019; 同理

只要x1<y1则答案呢为0。

如果l和r其中一个整除ans=0；

剩下的暴力枚举就行，因为最多就是2019*2019

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
int a[N],b[N],num[N];
int x[100][100];
ll n,m,k;
int main()
{scanf("%lld%lld",&n,&m);if(n%2019==0||m%2019==0) {cout<<0<<endl;return 0;}int x1=n/2019;int y1=m/2019; if(y1>x1){cout<<0<<endl;return 0;}ll ans=2020;for(ll i=n;i<=m;i++){for(ll j=i+1;j<=m;j++)ans=min((i%2019*j%2019)%2019,ans);}cout<<ans<<endl;return 0;
}

D - Rain Flows into Dams

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 400400 points

Problem Statement

There are NN mountains in a circle, called Mountain 11, Mountain 22, ......, Mountain NN in clockwise order. NN is an odd number.

Between these mountains, there are NN dams, called Dam 11, Dam 22, ......, Dam NN. Dam ii (1≤i≤N1≤i≤N) is located between Mountain ii and i+1i+1 (Mountain N+1N+1 is Mountain 11).

When Mountain ii (1≤i≤N1≤i≤N) receives 2x2x liters of rain, Dam i?1i?1 and Dam ii each accumulates xx liters of water (Dam 00 is Dam NN).

One day, each of the mountains received a non-negative even number of liters of rain.

As a result, Dam ii (1≤i≤N1≤i≤N) accumulated a total of AiAi liters of water.

Find the amount of rain each of the mountains received. We can prove that the solution is unique under the constraints of this problem.

Constraints

All values in input are integers.
3≤N≤105?13≤N≤105?1
NN is an odd number.
0≤Ai≤1090≤Ai≤109
The situation represented by input can occur when each of the mountains receives a non-negative even number of liters of rain.

Input

Input is given from Standard Input in the following format:

NN
A1A1 A2A2 ...... ANAN

Output

Print NN integers representing the number of liters of rain Mountain 11, Mountain 22, ......, Mountain NN received, in this order.

Sample Input 1 Copy

Copy

3
2 2 4

Sample Output 1 Copy

Copy

4 0 4

If we assume Mountain 11, 22, and 33 received 44, 00, and 44 liters of rain, respectively, it is consistent with this input, as follows:

Dam 11 should have accumulated 42+02=242+02=2 liters of water.
Dam 22 should have accumulated 02+42=202+42=2 liters of water.
Dam 33 should have accumulated 42+42=442+42=4 liters of water.

Sample Input 2 Copy

Copy

5
3 8 7 5 5

Sample Output 2 Copy

Copy

2 4 12 2 8

Sample Input 3 Copy

Copy

3
1000000000 1000000000 0

Sample Output 3 Copy

Copy

0 2000000000 0

题意：

给你n（奇数）座山，是一个环形的排列，第i与第i+1之间为第i座水坝，如果想第i座山泼水的质量为2*x，则第i-1和第i座水坝获得x的水量，问如果给你水坝的水量，求出向每一座山泼的水量？

分析：

上述关系可以整理为：a为水坝容水量，b为向山坡浇的水

a[i]=b[i]+b[i+1] i<n

a[i]=b[n]+b[1] i=n

a[1]=b[1]/2+b[2]/2

a[2]=b[2]/2+b[3]/2

a[3]=b[3]/2+b[1]/2

->

b[1]=a[1]-a[2]+a[3]

可以推规律了就。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
ll a[N],b[N],num[N];
int x[100][100];
int n,m,k;
int main()
{scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%lld",&a[i]);}for(int i=1; i<=n; i++){if(i%2==1)b[1]+=a[i];elseb[1]-=a[i];}for(int i=2;i<=n;i++){b[i]=2*a[i-1]-b[i-1];}for(int i=1;i<=n;i++){cout<<b[i]<<" ";}return 0;
}

E - Virus Tree 2

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 500500 points

Problem Statement

You are given a tree with NN vertices and N?1N?1 edges. The vertices are numbered 11 to NN, and the ii-th edge connects Vertex aiai and bibi.

You have coloring materials of KK colors. For each vertex in the tree, you will choose one of the KK colors to paint it, so that the following condition is satisfied:

If the distance between two different vertices xx and yy is less than or equal to two, xx and yy have different colors.

How many ways are there to paint the tree? Find the count modulo 1 000 000 0071 000 000 007.

What is tree?

What is distance?

Constraints

1≤N,K≤1051≤N,K≤105
1≤ai,bi≤N1≤ai,bi≤N
The given graph is a tree.

Input

Input is given from Standard Input in the following format:

NN KK
a1a1 b1b1
a2a2 b2b2
..
..
..
aN?1aN?1 bN?1bN?1

Output

Print the number of ways to paint the tree, modulo 1 000 000 0071 000 000 007.

Sample Input 1 Copy

Copy

Sample Output 1 Copy

Copy

There are six ways to paint the tree.

Sample Input 2 Copy

Copy

Sample Output 2 Copy

Copy

Sample Input 3 Copy

Copy

Sample Output 3 Copy

Copy

271414432

题意：

一棵树，n个节点，k种颜色，距离<=2的树不能冉同一种颜色，问方案数量？

分析：

距离为<=2的节点不能染相同的颜色,

我们首先假设一下这题只考虑一个距离为<=1的节点不能染相同的颜色,ans=k*（k-1）^(n-1)，即对于每一个点来说有几种可以选的颜色，如果父亲节点选了，选择有k种，则儿子节点不能选，只有（k-1）种，儿子的兄弟节点也只有相同的k-1种，儿子节点的儿子节点也有n-1种;

那么距离为<=2的叶子节点不能染相同的颜色,思想一样，考虑当前点可以选择的颜色个数。

如果父亲节点选了，选择有k种，则儿子节点不能选，只有（k-2）种，因为其父亲和祖父；

父亲的第二个孩子，只有相同的k-3种，因为其父亲和祖父和第一个孩子；

父亲的第三个孩子，只有相同的k-3种，因为其父亲和祖父和第一、二个孩子；

。。。。

但有一个坑点需要注意：当前节点为根，没有祖父，其孩子为k-1种选择

import syssys.setrecursionlimit(10**9)
#解决递归限制N, K = map(int, input().split())
mod = 1000000007def dfs(K, graph, now, source):if source == -1:can_use_color_num = K - 1else:can_use_color_num = K - 2if len(graph[now]) > K:return 0else:case_num = 1for dst in graph[now]:if dst == source:continuecase_num *= can_use_color_numcan_use_color_num -= 1case_num %= modfor dst in graph[now]:if dst == source:continuecase_num *= dfs(K, graph, dst, now)case_num %= modreturn case_numgraph = [[] for i in range(N)]
for i in range(N - 1):a, b = map(lambda x:int(x)-1, input().split())graph[a].append(b)graph[b].append(a)answer = K * dfs(K, graph, 0, -1)
answer %= mod
print(answer)