尽快将前面的练习补上&＃xff01;
每日一练
2.1
Problem A Laurenty and Shop
题意&＃xff1a;选择不同的两条路线使得总等待时间最小。
简析&＃xff1a;路线不同在于过马路的地方不同。
预处理前缀和&＃xff0c;可以O(1)得到走每条路时间&＃xff0c;挑选最小的两个即可。
1 #include
2 #include
3 using namespace std;
4 int a[2][50], b[50];
5 const int INF &＃61; 1e9;
6
7 int main(void)
8 {
9 int n;
10 scanf("%d", &n);
11 for(int i &＃61; 1; i
12 for(int i &＃61; 1; i
13 for(int i &＃61; 0; i
14 int A &＃61; INF, B &＃61; INF;
15 for(int i &＃61; 0; i
16 {
17 int pos &＃61; a[0][i] &＃43; b[i] &＃43; a[1][n-1] - a[1][i];
18 if(pos <&＃61; A) B &＃61; A, A &＃61; pos;
19 else if(pos
20 }
21 printf("%d\n", A &＃43; B);
22 return 0;
23 }
Problem B Gennady the Dentist
题意&＃xff1a;模拟牙医看病。
简析&＃xff1a;可以维护一个标记来判断小孩有没有逃走&＃xff0c;然后从前往后扫这个队列。
过程中进行两个操作&＃xff1a;
①看病&＃xff1a;按题意减去后面小孩的信心&＃xff0c;然后处理逃走。
②逃走&＃xff1a;给小孩标记出队&＃xff0c;给后面的人减去信心&＃xff0c;同时处理连锁反应。
1 #include
2 #include
3 #include
4 using namespace std;
5 const int maxn &＃61; 5000;
6 int v[maxn], d[maxn], p[maxn];
7 vector<int> ans;
8 bool out[maxn];
9 int n;
10
11 void run(int pos)
12 {
13 out[pos] &＃61; 1;
14 for(int i &＃61; pos &＃43; 1; i
15 {
16 if(out[i]) continue;
17 p[i] -&＃61; d[pos];
18 if(p[i] <0) run(i);
19 }
20 return;
21 }
22
23 void cure(int pos)
24 {
25 for(int i &＃61; pos &＃43; 1; i
26 {
27 if(v[pos] &＃61;&＃61; 0) break;
28 if(out[i]) continue;
29 p[i] -&＃61; v[pos], v[pos]--;
30 }
31 for(int i &＃61; pos &＃43; 1; i
32 {
33 if(out[i]) continue;
34 if(p[i] <0) run(i);
35 }
36 return;
37 }
38
39 int main(void)
40 {
41 scanf("%d", &n);
42 for(int i &＃61; 0; i
43 for(int i &＃61; 0; i
44 {
45 if(out[i]) continue;
46 ans.push_back(i);
47 cure(i);
48 }
49 printf("%d\n", ans.size());
50 for(int i &＃61; 0; i
51 puts("");
52 return 0;
53 }
2.2
Problem A Duff in Love
题意&＃xff1a;给出 一个 n ,找到最大的 x ,使得 x 满足 &＃xff0c;x 是 n 的因子&＃xff0c;并且x 的因子中没有平方数
简析&＃xff1a;将 n 分解质因数&＃xff0c;每个质因数取一个
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include<set>
8 using namespace std;
9
10 typedef long long LL;
11 const int maxn &＃61; 100005;
12 int dp[maxn];
13 int Max[maxn];
14 vector<int> p;
15
16 int vis[maxn];
17 int T,a[105];
18 int cnt[maxn];
19 set<long long > s;
20 LL n;
21
22 void solve( long long x){
23 LL y &＃61; x;
24 // printf("y &＃61; %I64d\n",y);
25 for(long long j &＃61; 2;1LL*j*j <&＃61; y;j&＃43;&＃43;){
26 if(y%j &＃61;&＃61; 0){
27 // printf("j &＃61; %I64d\n",j);
28 while(y%j &＃61;&＃61; 0){
29 s.insert(j);
30 y &＃61; y/j;
31 }
32 }
33 }
34 if(y > 1) s.insert(y);
35
36 // for(set
38 //}
39
40 }
41
42 void work(){
43 if(n &＃61;&＃61; 1){
44 puts("1");
45 return;
46 }
47 if(s.size() <2){
48 printf("%I64d\n",*s.begin());
49 return;
50 }
51 LL res &＃61; 1;
52 for(set<long long >::iterator it &＃61; s.begin();it !&＃61; s.end();&＃43;&＃43;it){
53 res &＃61; res*(*it);
54 }
55 printf("%I64d\n",res);
56 }
57
58 int main(){
59 while(scanf("%I64d",&n) !&＃61; EOF){
60 s.clear();
61 solve(n);
62 work();
63 }
64 return 0;
65 }
Problem B Duff and Weight Lifting
题意&＃xff1a;给出 n 个数&＃xff0c;如果满足 2^a1 &＃43; 2^a2 &＃43;...&＃43;2^ak &＃61; 2^x &＃61; S,则可以将 a1&＃xff0c;a2,...ak消掉&＃xff0c;问最少需要多少次消掉所有的数
简析&＃xff1a;从小到大的消&＃xff0c;两个 1 变成一个 2&＃xff0c;两个2变成一个3&＃xff0c;模拟这样的过程&＃xff0c;剩下的不能再合并的数的个数就是需要的操作数
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 using namespace std;
8
9 const int maxn &＃61; 1000005;
10 int a[maxn];
11 int n;
12
13 priority_queue<int,vector<int>,greater<int> > q;
14
15 int main(){
16 while(scanf("%d",&n) !&＃61; EOF){
17 while(!q.empty()) q.pop();
18
19 for(int i &＃61; 1;i <&＃61; n;i&＃43;&＃43;) scanf("%d",&a[i]),q.push(a[i]);
20
21 int c &＃61; 0;
22 while(!q.empty()){
23 if(q.size() >&＃61; 2){
24 int x &＃61; q.top();q.pop();
25 int y &＃61; q.top();q.pop();
26 if(x &＃61;&＃61; y) q.push(x&＃43;1);
27 else {
28 q.push(y);
29 c&＃43;&＃43;;
30 }
31
32 // printf("x &＃61; %d y &＃61; %d\n",x,y);
33 }
34 if(q.size() &＃61;&＃61; 1) {
35 int x &＃61; q.top();q.pop();
36 c&＃43;&＃43;;
37 }
38 if(q.size() &＃61;&＃61; 0) break;
39 }
40 printf("%d\n",c);
41
42 }
43
44 }
然后&＃xff0c;可以发现是在 统计 S 的二进制表现形式中 1 的个数
1 #include
2 #include
3 #include
4 #include
5 using namespace std;
6
7 const int maxn &＃61; 5e6&＃43;5;
8 int a[maxn],bit[maxn];
9 int n;
10
11 void solve(){
12 int ans &＃61; 0;
13 for(int i &＃61; 0;i
14 bit[i&＃43;1] &＃43;&＃61; bit[i]/2;
15 bit[i] &＃61; bit[i]%2;
16 ans &＃43;&＃61; bit[i];
17 }
18 printf("%d\n",ans);
19 }
20
21 int main(){
22 while(scanf("%d",&n)!&＃61; EOF){
23 memset(bit,0,sizeof(bit));
24 for(int i &＃61; 1;i <&＃61; n;i&＃43;&＃43;){
25 scanf("%d",&a[i]);
26 bit[a[i]]&＃43;&＃43;;
27 }
28 solve();
29 }
30 return 0;
31 }
可以再做一下这两题&＃xff0c;也和进制有关
Vanya and Scales
Slime Combining
2.3
Problem A Rebranding
题意&＃xff1a;给一个长度为n的字符串&＃xff0c;做m次字母替换&＃xff0c;求替换后的字符串。
简析&＃xff1a;先初始化一个字母表到自己本身的映射&＃xff0c;每一次替换&＃xff0c;把相应字母的象做一次交换。
最后根据交换完成后的映射&＃xff0c;将字符串转化成新串。
1 #include
2 #include
3 #include
4 using namespace std;
5 const int maxn &＃61; 2e5 &＃43; 10;
6 int pos[26], re[26];
7 char s[maxn];
8
9 int main(void)
10 {
11 int n, m;
12 scanf("%d %d %s", &n, &m, s);
13 for(int i &＃61; 0; i <26; i&＃43;&＃43;) pos[i] &＃61; i;
14 for(int i &＃61; 0; i
15 {
16 char x[5], y[5];
17 scanf("%s %s", x, y);
18 swap(pos[x[0]-&＃39;a&＃39;], pos[y[0]-&＃39;a&＃39;]);
19 }
20 for(int i &＃61; 0; i <26; i&＃43;&＃43;) re[pos[i]]&＃61;i;
21 for(int i &＃61; 0; i
22 puts("");
23 return 0;
24 }
Problem B Median Smoothing
题意&＃xff1a;给一个二进制串&＃xff0c;定义一种操作&＃xff1a;将101变为111,010变为000.问几次操作后该串不再变化。
简析&＃xff1a;首先要发现只有101和010会发生变化&＃xff0c;也即是说一旦出现了连续两个相同字符&＃xff0c;这两个字符就不会变。
我们除去所有连续相同的字符&＃xff0c;剩下的就只有01交错的串&＃xff0c;它们在经过一系列操作后会最终变为相同。
很容易发现要将一个长度为x的01交错串变为相同需要(x - 1) / 2次操作。
所以考虑所有的01交错串&＃xff0c;最长的那个决定了答案。
1 #include
2 #include
3 #include
4 using namespace std;
5 const int maxn &＃61; 5e5 &＃43; 10;
6 int a[maxn];
7
8 bool ok(int i)
9 {
10 return a[i] !&＃61; a[i-1] && a[i] !&＃61; a[i&＃43;1];
11 }
12
13 int main(void)
14 {
15 int n;
16 scanf("%d", &n);
17 for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;) scanf("%d", a &＃43; i);
18 int ans &＃61; 0;
19 for(int i &＃61; 2; i
20 {
21 if(ok(i))
22 {
23 int cnt &＃61; 0, p &＃61; i;
24 while(p
25 ans &＃61; max(ans, ( cnt &＃43; 1 ) / 2);
26 for(int j &＃61; 0; j <( cnt &＃43; 1 ) / 2; j&＃43;&＃43;)
27 a[i&＃43;j] &＃61; a[i&＃43;j-1], a[i&＃43;cnt-j-1] &＃61; a[i&＃43;cnt-j];
28 }
29 }
30 printf("%d\n", ans);
31 for(int i &＃61; 1; i <&＃61; n; i&＃43;&＃43;) printf("%d ",a[i]);
32 return 0;
33 }
2.4
Problem A The Monster and the Squirrel
题意&＃xff1a;给出一个 n 边形&＃xff0c;问收集完所有核桃需要跳多少次
简析&＃xff1a;找规律是 (n-2)*(n-2)
1 #include
2 #include
3 #include
4 #include
5 #include
6 #include
7 using namespace std;
8
9
10 typedef long long LL;
11 const int maxn &＃61; 1e5&＃43;5;
12 int n,m;
13 int a[maxn];
14
15 void solve(){
16 if(n &＃61;&＃61; 3){
17 puts("1");
18 return;
19 }
20
21 printf("%I64d\n",1LL*(n-2)*(n-2));
22 }
23
24 int main(){
25
26 while(scanf("%d",&n) !&＃61; EOF){
27 solve();
28 }
29 return 0;
30 }
Problem B The Big Race
题意&＃xff1a;A,B两人赛跑&＃xff0c;速度相等&＃xff0c;但是A的步长是 w,B 的步长是 b,跑道的长度 是 L&＃xff0c;在大于L的地方都是深渊&＃xff0c;A,B两人打成平手的条件是两人同时落入深渊
给出 t &＃xff0c;问[1,t] 内可以选择出多少个L&＃xff0c;输出个数与 t 的比
简析&＃xff1a;L 满足 L % w &＃61; L % b&＃xff0c;即L 满足
L &＃61; x*w &＃43; r &＃61; y*b &＃43; r -------------- (1)
在一个周期M &＃61; lcm(w,b)内&＃xff0c;满足 (1) 式的r 的个数 为 k &＃61; min(w,b)
证明&＃xff1a;在第一个 周期 [1,M] 内&＃xff0c;r 的取值范围是 [0,min(w,b)-1]
又因为需要 满足 (1)式子
所以&＃xff0c;L - r &＃61; x*w &＃61; y*b >&＃61; M
所以在 一个周期 lcm 内只有 min(w,b) 个
如果 t > M, 那么 ans &＃61; t/M * k &＃43; min(min(w,b)-1, t%M)
如果 t 在判断 t 和 M 的大小的时候&＃xff0c;可能会爆long long&＃xff0c;可以两边取一下 log 来判断大小关系 1 #include 2.5 Problem A BerSU Ball 题意&＃xff1a;男女skill相差不能超过1&＃xff0c;求最大匹配。 简析&＃xff1a;男女分别排序后&＃xff0c;从小到大扫一遍男&＃xff0c;贪心的尽可能先与小的女匹配。 1 #include Problem B Given Length and Sum of Digits... 题意&＃xff1a;求一共m位&＃xff0c;且每位数字和为s的最小的数与最大的数。 简析&＃xff1a;首先如果s为0且m大于1&＃xff0c;或者s大于9m是无解的。 最小的数只要先在最高位填1&＃xff0c;然后从最低位开始尽可能填9。 最大的数只要从最高位开始往后尽可能填9即可。 1 #include 2.6 Problem A Valuable Resources 题意&＃xff1a;给出n个点&＃xff0c;求包含这 n 个点的最小的正方形的面积 简析&＃xff1a;扫一遍求出 xmin 和 xmax,ymin,ymax,取 max(xmax-xmin,ymax-ymin) 作为边长 1 #include Problem B Bits 题意&＃xff1a;给出 n 个询问 &＃xff0c;求出在[1,r] 之间的 bitcount&＃xff08;x&＃xff09; 最大的x 简析&＃xff1a;从 l 开始一位一位的加 1直到大于 r 1 #include 2.7 Problem A Towers 题意&＃xff1a;最多进行k次移动单块操作&＃xff0c;使得最高塔与最低塔高度差最小。 简析&＃xff1a;因为数据很小&＃xff0c;反复排序把最高的移一个到最低的即可。 1 #include Problem B Exams 题意&＃xff1a;n门考试&＃xff0c;第$i$门可以在${a}_{i}$或者${b}_{i}$时考$(a > b)$&＃xff0c;但是登记仍按照${a}_{i}$&＃xff0c; 要求登记时间非严格递增&＃xff0c;问考完至少要几天。 简析&＃xff1a;先按照${a}_{i}$排序&＃xff0c;从前往后扫&＃xff0c;维护前几门考完的时间&＃xff0c; 如果这门${b}_{i}$大于等于前面考完的时间则提前考&＃xff0c;否则按原时间。 1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7
8 typedef long long LL;
9 LL t,w,b;
10
11 LL gcd(LL a,LL b){
12 return (!b)?a:gcd(b,a%b);
13 }
14
15 int sgn(double x){
16 if(fabs(x) <1e-6) return 0;
17 return x > 0?1:-1;
18 }
19
20 void solve(){
21 LL g &＃61; gcd(w,b);
22 LL fz &＃61; 0;
23 LL fm &＃61; t;
24 double cha &＃61; log(1.0*w)&＃43;log(1.0*b)-log(1.0*g)-log(1.0*t);
25 if(sgn(cha)>0){
26 fz &＃61; min(t,min(w,b)-1);
27 }
28 else{
29 LL lcm &＃61; (w/gcd(w,b))*b;
30 LL c &＃61; (t/lcm);
31 fz &＃61; c*min(w,b);
32 LL l1 &＃61; t%lcm;
33 LL l2 &＃61; t-c*lcm;
34 t &＃61; t%lcm;
35 fz &＃43;&＃61; min(t,min(w,b)-1);
36 }
37 LL gg &＃61; gcd(fz,fm);
38 printf("%I64d/%I64d\n",fz/gg,fm/gg);
39 }
40
41 int main(){
42 while(scanf("%I64d %I64d %I64d",&t,&w,&b) !&＃61; EOF){
43 solve();
44 }
45 return 0;
46 }
2 #include
3 #include
4 #include
5 using namespace std;
6 int a[111], b[111];
7
8 int main(void)
9 {
10 int n, m;
11 scanf("%d", &n);
12 for(int i &＃61; 0; i
13 scanf("%d", &m);
14 for(int i &＃61; 0; i
15 sort(a, a &＃43; n);
16 sort(b, b &＃43; m);
17 int j &＃61; 0, ans &＃61; 0;
18 for(int i &＃61; 0; i
19 {
20 if(j &＃61;&＃61; m) break;
21 if(abs(a[i] - b[j]) <&＃61; 1) j&＃43;&＃43;, ans&＃43;&＃43;;
22 else
23 {
24 while(j
25 if(abs(a[i] - b[j]) <&＃61; 1) j&＃43;&＃43;, ans&＃43;&＃43;;
26 }
27 }
28 printf("%d\n", ans);
29 return 0;
30 }
2 #include
3 #include
4 using namespace std;
5 int a[111], b[111];
6
7 int main(void)
8 {
9 int m, s;
10 scanf("%d %d", &m, &s);
11 if(!s && m > 1 || s > m * 9) puts("-1 -1");
12 else
13 {
14 int tmp &＃61; s;
15 for(int i &＃61; 1; i <&＃61; m; i&＃43;&＃43;)
16 tmp -&＃61; a[i] &＃61; min(tmp, 9);
17 tmp &＃61; s - 1;
18 b[1] &＃61; 1;
19 for(int i &＃61; m; i; i--)
20 b[i] &＃43;&＃61; min(tmp, 9), tmp -&＃61; min(tmp, 9);
21 for(int i &＃61; 1; i <&＃61; m; i&＃43;&＃43;) printf("%d", b[i]);
22 putchar(&＃39; &＃39;);
23 for(int i &＃61; 1; i <&＃61; m; i&＃43;&＃43;) printf("%d", a[i]);
24 }
25 return 0;
26 }
2 #include
3 #include
4 #include
5 using namespace std;
6
7 int a[1005],b[1005];
8 long long area;
9
10 int main()
11 {
12 int i,j,n;
13 long long ans1,ans2;
14 scanf("%d",&n);
15 for(i&＃61;0;i
16 {
17 cin>>a[i]>>b[i];
18 }
19 sort(a,a&＃43;n);
20 sort(b,b&＃43;n);
21
22 ans1&＃61;a[n-1]-a[0];
23 ans2&＃61;b[n-1]-b[0];
24 long long t&＃61;max(ans1,ans2);
25 printf("%I64d\n",t*t);
26 }
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7
8 typedef long long LL;
9
10 int main()
11 {
12 int n;
13 LL l,r;
14 scanf("%d",&n);
15 while(n--)
16 {
17 scanf("%I64d %I64d",&l,&r);
18 for(int i&＃61;0;i<63;i&＃43;&＃43;)
19 if((l|(1LL<
20
21 printf("%I64d\n",l);
22 }
23 }
2 #include
3 #include
4 #include
5 using namespace std;
6 typedef pair<int, int> pii;
7 vector
8 pii t[111];
9
10 int main(void)
11 {
12 int n, k;
13 scanf("%d %d", &n, &k);
14 for(int i &＃61; 0; i
15 {
16 scanf("%d", &t[i].first);
17 t[i].second &＃61; i &＃43; 1;
18 }
19 for(int i &＃61; 0; i
20 {
21 sort(t, t &＃43; n);
22 if(t[0].first &＃61;&＃61; t[n-1].first) break;
23 t[0].first&＃43;&＃43;, t[n-1].first--;
24 ans.push_back(pii(t[n-1].second, t[0].second));
25 }
26 sort(t, t &＃43; n);
27 printf("%d %d\n", t[n-1].first - t[0].first, ans.size());
28 for(int i &＃61; 0; i
29 return 0;
30 }
2 #include
3 #include
4 using namespace std;
5 typedef pair<int, int> pii;
6 pii c[5555];
7
8 int main(void)
9 {
10 int n;
11 scanf("%d", &n);
12 for(int i &＃61; 0; i
13 sort(c, c &＃43; n);
14 int ans &＃61; c[0].second;
15 for(int i &＃61; 1; i
16 ans &＃61; c[i].second >&＃61; ans ? c[i].second : c[i].first;
17 printf("%d\n", ans);
18 return 0;
19 }
京公网安备 11010802041100号