Codeforces Daily

每次读题都是伤.....

Math

 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int n, m, a;
 7     long long ans, x, y;
 8     cin >> n >> m >> a;
 9     x = n/a;
10     y = m/a;
11     if(n%a!=0) x++;
12     if(m%a!=0) y++;
13     ans = x*y;
14     cout << ans << endl;
15     return 0;
16 }
1A
 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string.h>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     int n, a, all = 0,ch1[105],ch2[105];
 9     memset(ch1,0,sizeof(ch1));
10     memset(ch2,0,sizeof(ch2));
11     cin >> n;
12     for(int i = 0; i < n; i++)
13     {
14         cin >> a;
15         ch1[a]++;
16     }
17     for(int i = 0; i < n; i++)
18     {
19         cin >> a;
20         ch2[a]++;
21     }
22     for(int i = 1; i <= 5; i++)
23     {
24         if((ch1[i]+ch2[i])%2 != 0)
25         {
26             cout << "-1
";
27             return 0;
28         }
29         if((ch1[i] + ch2[i])==0)
30             continue;
31         if((ch1[i]!=ch2[i]))
32         {
33             all += abs((ch1[i] - ch2[i])/2);
34         }
35     }
36     cout << all/2 << endl;
37     return 0;
38 }
779A
 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 struct stu{
 6     int a, b;
 7 }p[200010];
 8 
 9 int cmpa(stu x, stu y){
10     if(x.a==y.a)
11         return x.b < y.b;
12     return x.a < y.a;
13 }
14 
15 int cmpb(stu x, stu y){
16     if(x.b==y.b)
17         return x.a < y.a;
18     return x.b < y.b;
19 }
20 
21 long long solve(int a){
22     if(a < 2) return 0;
23     return (long long)a*(a-1)/2;
24 }
25 
26 int main()
27 {
28     int n;
29     cin >> n;
30     for(int i = 0; i < n; i++)
31         cin >> p[i].a >> p[i].b;
32     sort(p, p+n, cmpa);
33     int cnt = 1, t = 0, num = 1;
34     long long ans = 0;
35     for(int i = 1; i < n; i++)
36     {
37         if(p[i].a == p[t].a)
38             cnt++;
39         else
40         {
41             ans += solve(cnt);
42             t = i;
43             cnt = 1;
44         }
45     }
46     ans += solve(cnt);
47 
48     sort(p, p+n, cmpb);
49     t = 0, cnt = 1;
50     for(int i = 1; i < n; i++)
51     {
52         if(p[i].a == p[i-1].a && p[i].b == p[i-1].b)
53             num++;
54         else
55         {
56             ans -= solve(num);
57             num = 1;
58         }
59 
60         if(p[i].b == p[t].b)
61             cnt++;
62         else
63         {
64             ans += solve(cnt);
65             t = i;
66             cnt = 1;
67         }
68     }
69     ans -= solve(num);
70     ans += solve(cnt);
71     cout << ans << endl;
72     return 0;
73 }
650A

Dp

 1 #include <stdio.h>
 2 long long d[100010], ans[100010];
 3 int main()
 4 {
 5     int n,k,a,b;
 6     scanf("%d%d", &n, &k);
 7     for(int i = 0; i < k; i++)
 8         d[i] = 1;
 9     ans[0] = 0;
10     for(int i = k; i < 100010; i++)
11     {
12         d[i] = (d[i-1] + d[i-k])%1000000007;
13     }
14     for(int i = 1; i < 100010; i++)
15     {
16         ans[i] = (ans[i-1] + d[i])%1000000007;
17     }
18     while(n--)
19     {
20     scanf("%d%d", &a, &b);
21     printf("%I64d
", (1000000007+ans[b]-ans[a-1])%1000000007);
22     }
23     return 0;
24 }
474D
 1 #include<iostream>
 2 #include<string.h>
 3 #define MAX 100010
 4 using namespace std;
 5 
 6 
 7 int main()
 8 {
 9     int n, ch[MAX],b[MAX];
10     cin >> n;
11     memset(ch,0,sizeof(ch));
12     memset(b,0,sizeof(ch));
13     for(int i = 1; i <= n; i++)
14     {
15         cin >> ch[i];
16         if(ch[i] == ch[i-1])
17             b[i] = b[i-1];//b[i]表示上一个不同于该元素的元素的位置
18         else b[i] = i-1;
19     }
20     int ans =0;
21     for(int i= n; i > 0; i--)
22     {
23         int len = 1, j = i-1;
24         int num1 = ch[i];
25         int num2 = MAX;
26         while(j>0)
27         {
28             if(num1 == ch[j] || num2 == ch[j])
29             {
30                 len += j-b[j];
31                 j = b[j];
32             }
33             else if(num2 == MAX)
34             {
35                 num2 = ch[j];
36                 len += j-b[j];
37                 j = b[j];
38             }
39             else break;
40         }
41         ans = max(ans, len);
42         if(i < ans) break;
43     }
44     cout << ans << endl;
45     return 0;
46 }
602B

Brute_forces

 1 #include <iostream>
 2 #include <set>
 3 using namespace std;
 4 
 5 int ch1[105], ch2[105], ch3[105];
 6 
 7 int main()
 8 {
 9     int n;
10     while(cin >> n)
11     {
12         int x=0, y=0, z=0, a;
13         for(int i = 0; i < n; i++)
14         {
15             cin >> a;
16             if(a == 0) ch3[z++] = a;
17             else if(a > 0)
18             {
19                 ch2[y++] = a;
20             }
21             else ///a<0
22             {
23                 ch1[x++] = a;
24             }
25         }
26         if(y == 0)
27         {
28             ch2[y++] = ch1[--x];
29             ch2[y++] = ch1[--x];
30         }
31         if(x % 2 == 0)
32         {
33             ch3[z++] = ch1[--x];
34         }
35 
36         cout << x;
37         for(int i = 0; i < x; i++)
38             cout << " " << ch1[i];
39         cout << endl;
40 
41         cout << y;
42         for(int i = 0; i < y; i++)
43             cout << " " << ch2[i];
44         cout << endl;
45 
46         cout << z;
47         for(int i = 0; i < z; i++)
48             cout << " " << ch3[i];
49         cout << endl;
50     }
51     return 0;
52 }
300A
 1 #include <iostream>
 2 using namespace std;
 3 //
 4 int ch[200010];
 5 
 6 int main()
 7 {
 8     int n, t, c;
 9     cin >> n >> t >> c;
10     for(int i = 0; i < n; i++)
11         cin >> ch[i];
12     int i = 0, cou = 0, ans = 0;
13     while(i < n)
14     {
15         while(ch[i] <= t && i < n && cou < c)
16         {
17             cou++;
18             i++;
19         }
20         if(cou == c)
21         {
22             cou--;
23             ans++;
24         }
25         else
26         {
27             i++;
28             cou = 0;
29         }
30     }
31     cout << ans <<endl;
32     return 0;
33 }
427B

Greedy

 1 /*
 2 首先根据n^2的思路，我们用出现次数最多的数字来生成这个数列，
 3 即用它尽量构造长度越长的连续子数列，这样一定是最优的，因为
 4 这样一个数字若在中间可以同时影响其前后两个数字，举个例子:
 5 234这三个数字可以得到2个ai<ai+1的组数，而若不连续，2356，
 6 需要4个数才可以得到。根据这个构造思路我们还可以得到最后
 7 如果有剩下的数字那必然是出现次数最多的那个，假设现在出
 8 现次数最多的数字为a，a出现了cnt次，满足ai<ai+1的组数
 9 为ans=n-cnt。现在再加一个数字b进去，若a==b则按照最
10 优构造思路将其插到连续的a里，这样组数不变相当于
11 ans = (n + 1) - (cnt + 1) = n - cnt，若a!=b则
12 必然可以拿出来一个a和b组成一组，
13 即(n + 1) - cnt = n - cnt + 1 = ans + 1，
14 根据这样的归纳可以证得结论的正确性
15 
16 #include <cstdio>
17 #include <algorithm>
18 using namespace std;
19 int cnt[1005], n, tmp, ma;
20 
21 int main()
22 {
23     scanf("%d", &n);
24     for(int i = 0; i < n; i++)
25     {
26         scanf("%d", &tmp);
27         ma = max(ma, ++ cnt[tmp]);
28     }
29     printf("%d
", n - ma);
30 }
31 */
32 
33 #include <stdio.h>
34 #include <queue>
35 #include <vector>
36 using namespace std;
37 
38 int main()
39 {
40     int n, a, b;
41     priority_queue<int, vector<int>, greater<int> > q1;
42     priority_queue<int, vector<int>, greater<int> > q2;
43     scanf("%d", &n);
44     for(int i = 0; i < n; i++)
45     {
46         scanf("%d", &a);
47         q1.push(a);
48     }
49     int ans = 0;
50     while(q1.size() || q2.size())
51     {
52         if(q1.size())
53         {
54             a = q1.top();
55             q1.pop();
56         }
57         while(q1.size())
58         {
59             b = q1.top();
60             q1.pop();
61             if(b > a)
62             {
63                 ans++;
64                 a = b;
65             }
66             else q2.push(b);
67         }
68         if(q2.size())
69         {
70             a = q2.top();
71             q2.pop();
72         }
73         while(q2.size())
74         {
75             b = q2.top();
76             q2.pop();
77             if(b>a)
78             {
79                 ans++;
80                 a = b;
81             }
82             else q1.push(b);
83         }
84     }
85     printf("%d
", ans);
86     return 0;
87 }
651B

Constructive  Algorithms

 1 #include <iostream>
 2 using namespace std;
 3 
 4 long long ch[502][502];//多个数据相加
 5 
 6 int main()
 7 {
 8     int n;
 9     cin >> n;
10     if(n == 1)
11     {//特殊情况，其实感觉这里填什么正数都可以啊
12         cin >> n;
13         cout << "1" <<endl;
14     }
15     else
16     {
17         bool flag = false, now = true;
18         int x,y;
19         for(int i = 0; i < n; i++)
20             for(int k = 0; k < n; k++)
21             {
22                 cin >> ch[i][k];
23                 if(ch[i][k] == 0)
24                 {
25                     x = i;
26                     y = k;
27                 }
28             }
29         if(x == n-y-1 || x == y) flag = true;//在对角线上
30         long long sum = 0;
31         if(!flag)
32         {
33             for(int i = 0; i < n; i++)
34                 sum += ch[i][i];
35         }
36         else
37         {
38             if(x == 0)
39                 for(int i = 0; i < n; i++)
40                     sum += ch[1][i];
41             else
42                 for(int i = 0; i < n; i++)
43                     sum += ch[0][i];
44         }
45 
46         long long sum1 = 0;
47         for(int i = 0; i < n; i++)
48             sum1 += ch[x][i];
49         ch[x][y] = sum - sum1;
50         //··············检查
51 
52         for(int i = 0; i < n; i++)
53         {
54             sum1 = 0;
55             for(int k = 0; k < n; k++)
56                 sum1 += ch[i][k];
57             if(sum1 != sum)
58             {
59                 now = false;
60             }
61         }
62 
63         for(int i = 0; i < n; i++)
64         {
65             sum1 = 0;
66             for(int k = 0; k < n; k++)
67                 sum1 += ch[k][i];
68             if(sum1 != sum)
69             {
70                 now = false;
71             }
72         }
73         sum1 = 0;
74         for(int i = 0; i < n; i++)
75             sum1 += ch[i][i];
76             if(sum1 != sum)
77             {
78                 now = false;
79             }
80         sum1 = 0;
81         for(int i = 0; i < n; i++)
82             sum1 += ch[i][n-i-1];
83             if(sum1 != sum)
84             {
85                 now = false;
86             }
87         if(now && ch[x][y] > 0)
88             cout << ch[x][y];
89         else cout << "-1
";
90     }
91 
92     return 0;
93 }
711B
 

implementation

 1 #include <iostream>//没读懂题ac系列0.0  找到后面最小的一个交换
 2 using namespace std;
 3 
 4 int ch[3009],sh[3009][2];
 5 
 6 int main()
 7 {
 8     int n;
 9     cin >> n;
10     for(int i =0; i < n; i++)
11         cin >> ch[i];
12     int cnt = 0, mid;
13     for(int i = 0; i < n; i++)
14     {
15         int now = i;
16         for(int k = i+1; k < n; k++)
17         {
18             if(ch[now]>ch[k])
19             {
20                 now = k;
21             }
22         }
23         if(now!=i)
24         {
25             sh[cnt][0] = i;
26             sh[cnt][1] = now;
27             mid = ch[i];
28             ch[i] = ch[now];
29             ch[now] = mid;
30             cnt++;
31         }
32     }
33     cout << cnt <<endl;
34     for(int i = 0; i < cnt; i++)
35         cout << sh[i][0] << " " <<sh[i][1] <<endl;
36     return 0;
37 }
489A
 1 #include <iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     long long k;
 7     int n,ch[100010];
 8     cin >> n >> k;
 9     for(int i = 0; i < n; i++)
10         cin >> ch[i];
11     long long num = 0;
12     long long i;
13     for(i = 1; i <= n; i++)
14     {
15         num+=i;
16         if(num == k)
17         {
18             cout << ch[i-1]<<endl;
19             return 0;
20         }
21         else if(num > k)
22             break;
23     }
24     cout << ch[k-(num-i)-1] << endl;
25     return 0;
26 }
670B

Graph

 1 #include <iostream>
 2 #include <string.h>
 3 #include <vector>
 4 #include <queue>
 5 #define MAX 100010
 6 #define INF 9223372036854775800//因为是long long，所以用0x3f3f3f3f太小了
 7 using namespace std;
 8 
 9 int n,m;
10 
11 struct edge{
12     int to, cost;
13     edge(){}
14     edge(int to, int cost) : to(to), cost(cost){}
15 };
16 
17 vector <edge> ch[MAX];
18 typedef pair<long long, int> P;//length,point
19 long long d[MAX];//2*10e5 * 10e5 会超出int
20 int road[MAX];
21 int pre[MAX];
22 
23 
24 void dijkstra(){
25     priority_queue<P, vector<P>, greater<P> > que;
26     for(int i = 0; i <=n; i++)
27         d[i] = INF;
28     d[1] = 0;
29     que.push(P(0,1));
30 
31     while(que.size())
32     {
33         if(que.empty()) break;
34         P p = que.top(); que.pop();
35         int k = p.second;
36         if(d[k] < p.first)
37             continue;
38         for(int i = 0; i < ch[k].size(); i++)
39         {
40             edge e = ch[k][i];
41             if(d[e.to] > d[k] + e.cost)
42             {
43                 d[e.to] = d[k] + e.cost;
44                 que.push(P(d[e.to],e.to));
45                 pre[e.to] = k;
46             }
47         }
48     }
49 }
50 
51 
52 int main()
53 {
54     int a,b,c;
55     cin >> n >> m;
56     for(int i = 0; i < m; i++)
57     {
58         cin >> a >> b >> c;
59         ch[a].push_back(edge(b,c));
60         ch[b].push_back(edge(a,c));
61     }
62     dijkstra();
63     if(d[n] == INF)
64     {
65         cout<<"-1
";
66         return 0;
67     }
68     int now = n, cou = 0;
69     while(now != 1)
70     {
71         road[cou++] = now;
72         now = pre[now];
73     }
74     road[cou++] = 1;
75     for(int i = cou-1; i >= 0; i--)
76         cout<< road[i]<<" ";
77     return 0;
78 }
20C

Sorting

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7     int n,ch[100010];
 8     cin >> n;
 9     for(int i = 0; i < n; i++)
10         cin >>ch[i];
11     sort(ch,ch+n);
12     int ans = 0;
13     for(int i = 0; i < n; i++)
14     {
15         if(ch[i] > ans)
16             ans++;
17     }
18     cout << ans+1 <<endl;
19     return 0;
20 }
21 /*在非递减序列中，求不能连续到达的最小的数
22 如果数组元素的值比下标大，那么数组可以减小
23 
24 
25 */
682B
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/tony-/p/6718448.html