第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南）(热身赛)

A 2020

题意：给出一个数n（<1e18），判断1到n中有几个数是循环的（比如2020,1111是，111就不是）
思路：首先想到对于一个数满足条件，其位数肯定是个偶数，所以可以打表两位的一共有9个，四位的一共有90个，以此类推。然后对于大于位数的部分，找规律处理下。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int num[100];
int main(){
	num[2] = 9; num[4] = 90;
	num[6] = 900;  num[8] = 9000;
	num[10] = 90000; num[12] = 900000;
	num[14] = 9000000;  num[16] = 90000000;
	num[32] = 900000000;
	
	string s; cin>>s; int n=s.size();
	LL ans = 0;
	for(int i = 0; i < n; i+=2)
		ans += num[i];
	
	if(s.size()%2==1){	
		cout<<ans<<"\n";
		return 0;
	}
	
	string t1 = s.substr(0,n/2), t2 = s.substr(n/2);
	LL tmp = 0;
	for(int i = 0; i < t1.size(); i++){
		tmp = tmp*10+t1[i]-'0';
		if(i==0)tmp--;
	}
	
	if(t2>=t1){
		cout<<tmp+1+ans<<"\n";
		return 0;
	}else{
		cout<<tmp+ans<<"\n";
	}
	return 0;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
 

B Four Xor

题意：给出一个长为n的排列（n<1e5,ai<1e5），求是否存在随机选四个数满足异或起来结果为0.
思路：暴力枚举每个数和其他数异或起来的结果，如果某个结果出现了两次（即这四个数异或为零），输出Yes即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
int a[maxn], m[maxn];

int main(){
	ios::sync_with_stdio(false);
	int n;  cin>>n;
	for(int i=1; i<=n; i++)cin>>a[i];
	if(n > 1000){
		cout<<"Yes\n"; return 0;
	}
	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			m[a[i]^a[j]]++;
			if(m[a[i]^a[j]]>=2){
				cout<<"Yes\n";
				return 0;
			}
		}
	}
	cout<<"No\n";
	return 0;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
 

C GPA

题意：按顺序给出n天的成绩ai，如果第i天的成绩小于前i-1天的平均数则悲伤。现在可以修改ai为bi，求任意修改后他最少的悲伤天数。
思路：考虑dp，令状态f(i,j)表示到第i天为止，伤心j天需要的最小成绩。转移：对于第i天，如果可以不伤心（<a[i]*(i-1)）则更新f(i,j)。如果一定要伤心了则更新f(i,j+1)。再考虑更换为bi后，如果不伤心了，再更新一次。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 4010;
int a[maxn], b[maxn], f[maxn][maxn];
int main(){
	int n;  cin>>n;
	for(int i =1; i <=n; i++){
		cin>>a[i]>>b[i];
		if(a[i]>b[i])swap(a[i],b[i]);
	}
	memset(f,0x3f,sizeof(f));
	f[1][0] = min(a[1],b[1]);
	for(int i = 2; i <= n; i++){
		for(int j = 0; j < i; j++){
			if(f[i-1][j]<=a[i]*(i-1)){
				f[i][j] = min(f[i][j], f[i-1][j]+a[i]);
			}else{
				f[i][j+1] = min(f[i][j+1],f[i-1][j]+a[i]);
				if(f[i-1][j]<=b[i]*(i-1))f[i][j]=min(f[i][j],f[i-1][j]+b[i]);
			}
		}
	}
	int ans = 1e9;
	for(int i = 0; i <= n; i++)if(f[n][i]<1e9){ans=i;break;}
	cout<<ans<<"\n";
	return 0;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/111770954