Codeforces Round 239 Div 1

首页 > 代码库 > Codeforces Round 239 Div 1

2024-07-06 06:50:10 225人阅读

都怪自己太懒了这段时间比赛参加了大部分，但是一直都没写题解，趁这几天没事，计划把这段时间的题解都补上。

上一次比赛（248）终于升到了div1，所以从这次开始就开始写div1了。

A. Triangle

There is a right triangle with legs of length a and b. Your task is to determine whether it is possible to locate the triangle on the plane in such a way that none of its sides is parallel to the coordinate axes. All the vertices must have integer coordinates. If there exists such a location, you have to output the appropriate coordinates of vertices.

Input

The first line contains two integers a,?b (1?≤?a,?b?≤?1000), separated by a single space.

Output

In the first line print either "YES" or "NO" (without the quotes) depending on whether the required location exists. If it does, print in the next three lines three pairs of integers — the coordinates of the triangle vertices, one pair per line. The coordinates must be integers, not exceeding 10⁹ in their absolute value.

Sample test(s)

input

1 1

output

input

5 5

output

YES
2 1
5 5
-2 4

input

5 10

output

YES
-10 4
-2 -2
1 2

应该算是数学题吧，有点坑啊，赛后交了六七次。。。（┬＿┬）

我的思路是：固定一个点在（0,0）（记为O），剩下两个点（分别记为A,B）分别放在第二象限和第一象限。枚举A和B点的横坐标，就可相同，这样第三条边就会和X轴平行了，这个时候要分别各自交换A、B横纵坐标就可以了。

代码有点丑（┬＿┬）

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef pair<int,int> PII;
 4 typedef pair<string,int> PSI;
 5 typedef map<string,int> MSI;
 6 typedef long long LL;
 7 template<class T> T sqr(T x) {return x*x;}
 8 template<class T> T f_abs(T x) {return x > 0 ? x : -x;}
 9 #define PI acos(-1)
10 #define MAXLONGINT 2147483647
11 #define INT 1e10
12 #define X first
13 #define Y second
14 #define PB push_back
15 #define MP mack_pair
16 #define debug(x) cerr<<#x" = "<<(x)<<endl
17 #define foreach(it,v) for (__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
18 
19 int main()
20 {
21     int a,b; cin>>a>>b;
22     int wqpfs[1000005], pfg[1000005];
23     memset(wqpfs,0,sizeof(wqpfs));
24     for(int i = 1; i <= max(a,b); i++)
25     {
26         wqpfs[i*i] = 1;
27         pfg[i*i] = i;
28     }
29     int ansed = 0;
30     for(int i = 1; i <= max(a,b); i++)
31     {
32         int ta = a*a - i*i;
33         if(ta < 0) break;
34         if(!wqpfs[ta]) continue;
35         int ax = -i, ay = pfg[ta];
36         for(int j = 1; j <= max(a,b); j++)
37         {
38             int tb = b*b - j*j;
39             if(tb < 0) break;
40             if(!wqpfs[tb]) continue;
41             int bx = j, by = pfg[tb];
42             int c = sqr(ax - bx) + sqr(ay - by);
43             if(c == sqr(a) + sqr(b))
44             {
45                 ansed = 1;
46                 if(ay == by)
47                 {
48                     swap(bx,by);
49                     swap(ax,ay);
50                     ax = -ax; ay = -ay;
51                 }
52                 cout<<"YES"<<endl
53                     <<"0 0"<<endl
54                     <<ax<<‘ ‘<<ay<<endl
55                     <<bx<<‘ ‘<<by<<endl;
56                 break;
57             }
58         }
59         if(ansed) break;
60     }
61     if(!ansed)
62     {
63         cout<<"NO"<<endl;
64     }

View Code

B. Long Path

One day, little Vasya found himself in a maze consisting of (n?+?1) rooms, numbered from 1 to (n?+?1). Initially, Vasya is at the first room and to get out of the maze, he needs to get to the (n?+?1)-th one.

The maze is organized as follows. Each room of the maze has two one-way portals. Let‘s consider room number i (1?≤?i?≤?n), someone can use the first portal to move from it to room number (i?+?1), also someone can use the second portal to move from it to room numberpi, where 1?≤?pi?≤?i.

In order not to get lost, Vasya decided to act as follows.

Each time Vasya enters some room, he paints a cross on its ceiling. Initially, Vasya paints a cross at the ceiling of room 1.
Let‘s assume that Vasya is in room i and has already painted a cross on its ceiling. Then, if the ceiling now contains an odd number of crosses, Vasya uses the second portal (it leads to room pi), otherwise Vasya uses the first portal.

Help Vasya determine the number of times he needs to use portals to get to room (n?+?1) in the end.

Input

The first line contains integer n (1?≤?n?≤?103) — the number of rooms. The second line contains n integers pi (1?≤?pi?≤?i). Each pidenotes the number of the room, that someone can reach, if he will use the second portal in the i-th room.

Output

Print a single number — the number of portal moves the boy needs to go out of the maze. As the number can be rather large, print it modulo 1000000007 (109?+?7).

Sample test(s)

input

2
1 2

output

input

4
1 1 2 3

output

input

5
1 1 1 1 1

output

62


    难得能遇到这么简单的题 很简单的DP
    状态转移方程 dp[i] = 2*dp[i-1] - dp[p[i]-1] + 2; 其中dp[i]表示从第1个房间到第i+1个房间所要经过的portal的总数，p[i]如题意所示
    简单解释一下，这样写应该比较好理解 dp[i] = dp[i-1] + 1 + (dp[i-1] - dp[p[i]-1]) + 1; dp[i-1]表示第一次到i号房间所需要经过的portal数，之后的 1 表示从second portal返回到p[i]号房间，(dp[i-1] - dp[p[i]-1])表示从p[i]号房间到i号房间所需要经过的portal数，最后的 1 表示从first portal到 i+1 号房间
需要注意的是： 
    要求答案对 1e9+7 取模
    一开始我是这样写的 dp[i] = (2*dp[i-1] - dp[p[i]-1] + 2) % M; （M 表示 1e9+7）这样的问题是某次取模后可能会使 dp[i-1] 非常小，导致 2*dp[i-1] - dp[p[i]-1] + 2 < 0，这样取模后就会导致答案可能会是个负数，然后就WA了
    之后我改成了 dp[i] = (2*dp[i-1] - dp[p[i]-1] + 2 + M) % M; 然后还是WA了。这回的原因是某次取模后可能会使 dp[i-1] 非常大，导致 2*dp[i-1] - dp[p[i]-1] + 2 超过了 MAXLONGINT
    看了几个大神的代码，改成了这样 dp[i] = (2*dp[i-1]%M - dp[p[i]-1] + M + 2) % M; 这样就可以防止超过 MAXLONGINT 而导致的溢出  
    又试了一个比较丑的写法 dp[i] = ((LL)(2*dp[i-1]%M - dp[p[i]-1] + M) + 2) % M; （LL 表示 long long）
    最后试了一下直接把 dp 数组定义成 long long 也一样AC了

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef pair<int,int> PII;
 4 typedef pair<string,int> PSI;
 5 typedef map<string,int> MSI;
 6 typedef long long LL;
 7 template<class T> T sqr(T x) {return x*x;}
 8 template<class T> T f_abs(T x) {return x > 0 ? x : -x;}
 9 #define PI acos(-1)
10 #define MAXLONGINT 2147483647
11 #define INT 1e10
12 #define X first
13 #define Y second
14 #define PB push_back
15 #define MP mack_pair
16 #define debug(x) cerr<<#x" = "<<(x)<<endl
17 #define foreach(it,v) for (__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
18 #define MAXN 1005
19 #define M 1000000007
20 
21 int main()
22 {
23     int n; cin>>n;
24     LL p[MAXN],dp[MAXN];
25     dp[0] = p[0] = 0;
26     for(int i = 1; i <= n; i++)
27     {
28         cin>>p[i];
29         dp[i] = (2*dp[i-1]%M - dp[p[i]-1] + M + 2) % M;
30     }
31     cout<<dp[n]<<endl;
32     return 0;
33 }

View Code

C. Curious Array

You‘ve got an array consisting of n integers: a[1],?a[2],?...,?a[n]. Moreover, there are m queries, each query can be described by three integers li,?ri,?ki. Query li,?ri,?ki means that we should add $\text{[math]}$ to each element a[j], where li?≤?j?≤?ri.

Record $\text{[math]}$ means the binomial coefficient, or the number of combinations from y elements into groups of x elements.

You need to fulfil consecutively all queries and then print the final array.

Input

The first line contains integers n, m (1?≤?n,?m?≤?105).

The second line contains n integers a[1],?a[2],?...,?a[n] (0?≤?ai?≤?109) — the initial array.

Next m lines contain queries in the format li,?ri,?ki — to all elements of the segment li... ri add number $\text{[math]}$ (1?≤?li?≤?ri?≤?n; 0?≤?k?≤?100).

Output

Print n integers: the i-th number is the value of element a[i] after all the queries. As the values can be rather large, print them modulo1000000007 (109?+?7).

Sample test(s)

input

5 1
0 0 0 0 0
1 5 0

output

1 1 1 1 1

input

10 2
1 2 3 4 5 0 0 0 0 0
1 6 1
6 10 2

output

2 4 6 8 10 7 3 6 10 15

    好题，数学题

    这题一个简化版就是 k = 0 的情况：也就是说给定一个数列a[i]和若干区间，给区间内所有数加上1，然后问执行完所有加法操作后，数列里每个数是多少
    线段树是可以做到在线的O(nlgn)级别的算法，不过这题只要离线的就可以，于是可以用前缀和数组（姑且这么叫）来做
    也就是说令 b[i] = a[i] - a[i-1]; 那么 a[i] = b[1] + b[2] + ... + b[i];  那么对于区间 [L,r] 进行 +1 这个操作， 只要对数组 b[L]++; b[r+1]--; 就可以了

    这题是上述那个题的拓展 
    考虑 k = 1 的情况，也就是说对于区间[L,r]，我们要进行 对区间里每个数分别 +1,+2,...,+(r-L+1) 这样的操作
    我们令 b[i] = a[i] - a[i-1]; c[i] = b[i] - b[i-1]; 
    现在只要对数组 c[L]++; c[r+1]--; b[r+1] -= r-L+1; 就可以了

    同理，对于任意的 k 我们需要执行以下的操作
    1.a[L][k] += 1;
    2.a[r+1][j] -= C[r-L+k-j][k-j] 其中C[m][n]表示组合数，0 <= j <= k;
    最后再做 k 遍前缀和就好啦，具体怎么做看代码

    PS：1.这题同样要求对答案取模 被这个坑了6 7回 下面两个地方的取模要注意
          c[i][j] = (c[i-1][j-1] + c[i-1][j]) % M;
          a[r+1][j] = (a[r+1][j] - c[r-L+k-j][k-j]) % M;
        2.我知道 我写的题解好烂 （┬＿┬）  相信我，我以后会努力的
          看不下去 英文好的可以看一下 官方的题解
          http://codeforces.com/blog/entry/11333

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef pair<int,int> PII;
 4 typedef pair<string,int> PSI;
 5 typedef map<string,int> MSI;
 6 typedef long long LL;
 7 template<class T> T sqr(T x) {return x*x;}
 8 template<class T> T f_abs(T x) {return x > 0 ? x : -x;}
 9 #define PI acos(-1)
10 #define MAXLONGINT 2147483647
11 #define INT 1e10
12 #define X first
13 #define Y second
14 #define PB push_back
15 #define MP mack_pair
16 #define debug(x) cerr<<#x" = "<<(x)<<endl
17 #define foreach(it,v) for (__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
18 #define MAXN 100105
19 #define M 1000000007
20 
21 int main()
22 {
23     int n,m; cin>>n>>m;
24     int ori[MAXN], a[MAXN][105], c[MAXN][105];
25     LL sum[MAXN];
26     for(int i = 1; i <= n; i++)
27     {
28         cin>>ori[i];
29         ori[i] %= M;
30     }
31     c[0][0] = 1;
32     for(int i = 1; i <= MAXN-5; i++)
33     {
34         for(int j = 0; j <= min(100,i); j++)
35         {
36             if(0 == j) c[i][j] = 1;
37             else c[i][j] = (c[i-1][j-1] + c[i-1][j]) % M;
38         }
39     }
40     memset(sum, 0, sizeof(sum));
41     memset(a, 0, sizeof(a));
42     int L,r,k,maxk = 0;
43     for(int i = 1; i <= m; i++)
44     {
45         cin>>L>>r>>k;
46         maxk = max(maxk, k);
47         a[L][k]++;
48         for(int j = 0; j <= k; j++)
49         {
50             a[r+1][j] = (a[r+1][j] - c[r-L+k-j][k-j]) % M;
51         }
52     }
53     for(int i = maxk; i >= 0; i--)
54     {
55         for(int j = 1; j <= n; j++)
56         {
57             sum[j] = (sum[j] + sum[j-1] + a[j][i]) % M;
58         }
59     }
60     for(int i = 1; i <= n; i++)
61     {
62         sum[i] = (sum[i] + ori[i] + M) % M;
63     }
64     for(int i = 1; i != n; i++)
65     {
66         cout<<sum[i]<<‘ ‘;
67     }
68     cout<<sum[n]<<endl;
69     return 0;
70 }

View Code

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > Codeforces Round 239 Div 1

Codeforces Round 239 Div 1

看完仍有疑问？有类似问题直接问程序猿