Codeforces Round #239 (Div. 2)

时间：2014-04-02 11:24:02 阅读：586 评论：0 收藏：0 [点我收藏+]

没事扯淡再写篇题解吧！反正只会大众题目。

题意：给出n个队列以及每个人付费所需要的时间求出用时最短的一条队列。

sl: 比较逗比(叙述这么长)的水体，5分钟1Y 。

1 #include<cstdio>

2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 const int MAX = 100+10;
6 const int inf = 0x3f3f3f3f;
7 int k[MAX];
8 int main()
9 {
10     int n; int a; int ret,ans;
11     while(scanf("%d",&n)==1)
12     {
13         ret=0; ans=inf;
14         for(int i=0;i<n;i++) scanf("%d",&k[i]);
15         for(int i=0;i<n;i++)
16         {
17             ret=0;
18             for(int j=0;j<k[i];j++)
19             {
20                 scanf("%d",&a);
21                 ret+=(15+a*5);
22             }
23             ans=min(ret,ans);
24         }
25         printf("%d\n",ans);
26     }
27     return 0;
28 }

B：

题意：给出一个字符串代表相应颜色的彩纸（S=1）。然后又给出自己需要的彩纸，求得到的最大的彩纸的面积。

sl: 无以言状的水题（没办法只会这种）,直接模拟就好了。

1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 const int MAX = 1e3+10;
6 char str1[MAX],str2[MAX];
7 int cnt1[40],cnt2[40];
8 int main()
9 {
10     int ans=0,flag;
11     while(scanf("%s %s",str1,str2)==2)
12     {
13         flag=1;
14         int n=strlen(str1);
15         int m=strlen(str2);
16         memset(cnt1,0,sizeof(cnt1));
17         memset(cnt2,0,sizeof(cnt2));
18         for(int i=0;i<n;i++) cnt1[str1[i]-‘a‘]++;
19         for(int i=0;i<m;i++) cnt2[str2[i]-‘a‘]++;
20         for(int i=0;i<40;i++)
21         {
22             if(cnt1[i]>=cnt2[i]) ans+=cnt2[i];
23             else if(cnt1[i]<cnt2[i]&&cnt1[i]!=0) ans+=cnt1[i];
24             else if(!cnt1[i]&&cnt2[i])
25             {
26                 flag=0;
27                 break;
28             }
29         }
30         if(flag) printf("%d\n",ans);
31         else printf("-1\n");
32     }
33     return 0;

34 }

题意：给出一个直角三角形的两条直角边的长度问是不是存在一组整点，使得直角三角形的任意一条边都不平行于坐标系。

sl：其实是道很水的题目。就是疯狂wa。主要是少考虑一种情况，就是当斜边平行于y轴的时候。

考虑到这种情况就简单了。直接枚举边a,那么边b可以通过方程组

x*i+y*i=0;

x^2+y^2=b^2;

得到。

1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 #include<cmath>
5 using namespace std;
6 typedef long long LL;
7 const int MAX = 3000+10;
8 LL xx,yy,x,y;
9 LL a,b;
10 int check(LL i,LL j)
11 {
12     LL L=i*i+j*j;
13     if(L!=a*a) return 0;
14     x=i; y=j;
15     double ans=(double)(i*i*b*b)/(double)(i*i+j*j);
16     //printf("%lf\n",ans);
17     if(ans-(LL)ans!=0) return 0;
18     else ans=sqrt(ans);
19     if(ans-(LL)ans!=0) return 0;
20     yy=(LL)ans; yy=-yy;
21     ans=-yy*j/(double)i;
22     if(ans-(LL)ans!=0) return 0;
23     xx=(LL)ans;
24
25     if(xx==x) return 0;
26     return 1;
27 }
28 int main()
29 {
30     while(scanf("%I64d %I64d",&a,&b)==2)
31     {
32         int m=max(a,b); int flag=0;
33         for(int i=1;i<m+2&&!flag;i++)
34         {
35             for(int j=1;j<m+2&&!flag;j++)
36             {
37                 if(check((LL)i,(LL)j))
38                 {
39                     flag=1;
40                     break;
41                 }
42             }
43         }
44         if(!flag) printf("NO\n");
45         else
46         {
47             printf("YES\n0 0\n");
48             printf("%I64d %I64d\n%I64d %I64d\n",xx,yy,x,y);
49         }
50     }
51
52     return 0;

53 }

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 number pi, 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 pi denotes 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 modulo1000000007 (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

题意:给出n+1个房间,p【i】数组就是每一次从i房跳到p[i]房。每次经过i点都要先在 i 房间画上一个十字。

满足当i房的十字为奇数时要跳到p[i]房间。偶数跳到i+1号房间。问走到n+1号房间需要多少步。

sl: 还是比较水，tourise 9min 1Y卧槽。杂家要想一个小时。

可以知道如果一个人走到 i房间那么i之前的房间肯定有偶数个十字。这样设走到i房间花偶数个十字的步数为

dp[i]。那么下一次跳到p[i] ，之后p[i]十字变为奇数，走的步数为dp[p[i]]。这样一直从p[i]加到i就是走到i应该走的步数。

所以只要从头到尾扫一遍就好了。

1 #include<cstdio>

2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 const int MAX = 1e3+10;
6 const int MOD = 1e9+7;
7 int dp[MAX],p[MAX];
8 int main()
9 {
10     int n,ans=0;
11     while(scanf("%d",&n)==1)
12     {
13         for(int i=1;i<=n;i++) scanf("%d",&p[i]);
14         memset(dp,0,sizeof(dp));
15         dp[1]=2; ans=dp[1];
16         for(int i=2;i<=n;i++)
17         {
18             dp[i]=2;
19             for(int j=p[i];j<i;j++)
20             dp[i]=(dp[i]+dp[j])%MOD; //加上之前走的步数
21             ans=(ans+dp[i])%MOD;
22         }
23         printf("%d\n",ans);
24     }
25     return 0;
26 }

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 integersli,?ri,?ki. Query li,?ri,?ki means that we should add bubuko.com,布布扣 to each element a[j], where li?≤?j?≤?ri.

Record bubuko.com,布布扣 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 bubuko.com,布布扣 (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

题意：给出一组数列。然后给出一组查询，每次都在相应区间加上相应的值，求最终的序列。

sl: 就是被这道题打入了畜道。sol以后再补。。。

Codeforces Round #239 (Div. 2),布布扣,bubuko.com

Codeforces Round #239 (Div. 2)

原文：http://www.cnblogs.com/acvc/p/3636793.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)