第二次测试部分题解 (c,d,g)

c-一个欧拉函数模板题

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int n;
 7     cin >> n;
 8     int r = n;
 9     for (int i = 2; i * i <= n; i++)
10     {
11         if (n % i == 0)
12         {
13             r = r / i * (i - 1);
14             while (n % i == 0)
15                 n /= i;
16         }
17     }
18     if (n > 1)
19         r = r / n * (n - 1);
20     cout << r;
21     return 0;
22 }

d-机器翻译

 1 #include<iostream>
 2 using namespace std;
 3 int wen[1005],shu[1005];
 4 int n, m, sum,s;
 5 
 6 int main()
 7 {
 8     cin >> n >> m;
 9     int k = 0,i=0;
10     while (m--)
11     {
12         cin >> s;
13         if (shu[s] == 0)   //记录是不是重复数字
14         {
15             sum++;
16             wen[k++] = s;
17             shu[s] = 1;
18             if (k > n)  //当第一次k>n后每一次加数字都需要删除当前最先加入的数字
19                 shu[wen[i++]] = 0;  //删除了把标记数字清0
20         }
21     }
22     cout << sum << endl;
23     return 0;
24 }

g-借教室（前缀和加二分）

 1 #include<iostream>
 2 using namespace std;
 3 const int N = 1e6 + 5;
 4 int shu[N], d[N], l[N], r[N], z[N];
 5 int n, m,s,nu,l1,r1,xu;
 6 
 7 bool er(int x)  //判断能不能完成
 8 {
 9     memset(z, 0, sizeof(z));
10     xu = 0;
11     for (int i = 1; i <= x; i++)  //z为借教室差分数组
12     {
13         z[l[i]] += d[i];
14         z[r[i] + 1] -= d[i];
15     }
16     for (int i = 1; i <= n; i++)
17     {
18         xu += z[i];  //xu为当天需要的教室
19         if (xu > shu[i]) return 0;
20     }
21     return 1;
22 }
23 
24 int main()
25 {
26     cin >> n >> m;
27     for (int i = 1; i <= n; i++)
28         cin >> shu[i];
29     for (int i = 1; i <= m; i++)
30         cin >> d[i] >> l[i] >> r[i];
31     l1 = 1; r1 = m;
32     if (er(m)) cout << '0';
33     else
34     {
35         while (l1 < r1)
36         {
37             int mid = (l1 + r1)/  2;
38             if (er(mid)) l1 = mid +1;
39             else r1 = mid ;
40         }
41         cout << -1 << endl << l1;
42     }
43     return 0;
44 }