2017ccpc秦皇岛 zoj 3981(A) 题目要求 第一行三个数字n, m, q表示有m个座位围成一个环，n个队伍，q次A题
参考AC代码 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
using namespace std;
int T,n,m,q;
LL s[maxn],t[maxn];
int main
// freopen("input.txt" ,"r" ,stdin);
scanf("%d" ,&T);
while (T--){
scanf("%d%d%d" ,&n,&m,&q);
for (int i=1;i<=n;i++) scanf("%lld" ,&s[i]);
LL sum=0,ans=1e18;
for (int i=1;i<=q;i++){
LL a,b;
scanf("%lld%lld" ,&a,&b);
t[i]=(s[a]-1-b+m)%m;
sum+=t[i];
}
sort(t+1,t+1+q);
for (int i=1;i<=q;i++){
ans=min(ans,sum+(LL)m*(i-1)-t[i]*q);
}
printf ("%lld\n" ,ans);
}
return 0;
}
思路 假设机器人位置在1位置上 对于每个a b 那么每次产生的不开心值就是s[a]-1-b 如果是负值 +m mod m
zoj 3983(C) 题目要求 给出由字符g a o组成的9个字符串 每个字符各出现3次
参考AC代码 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
38
39
using namespace std;
int t,ans;
string s;
void dfs(string str,int cnt){
vector<pair<int,int> >re;
int len=str.length();
if (len==0){
ans=max(ans,cnt);
return ;
}
int cur=0;
for (int i=0;i<len;i++){
if (str[i]!=str[cur]){
re.push_back(make_pair(cur,i));
cur=i;
}
}
re.push_back(make_pair(cur,len));
for (auto p:re){
string temp=str;
temp.erase(temp.begin()+p.fi,temp.begin()+p.se);
if (p.se-p.fi==3) dfs(temp,cnt+1);
else dfs(temp,cnt);
}
}
int main
// freopen("input.txt" ,"r" ,stdin);
scanf("%d" ,&t);
while (t--){
cin>>s;
ans=0;
dfs(s,0);
cout<<ans<<endl;
}
return 0;
}
思路 dfs暴搜
zoj 3987(G) 参考AC代码 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
import java.util.*;
import java.math.*;
public class Main{
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
BigInteger x0 = BigInteger.valueOf(0);
BigInteger x1 = BigInteger.valueOf(1);
BigInteger x2 = BigInteger.valueOf(2);
BigInteger []b = new BigInteger[5005];
b[0]=x1;
for (int i=1;i<5000;i++)
b[i]=b[i-1].multiply(x2);
int T = cin.nextInt();
for (int t=1;t<=T;t++){
BigInteger n=cin.nextBigInteger();
BigInteger m=cin.nextBigInteger();
BigInteger top = n.add(m.subtract(x1)).divide(m);
int len = 0;
while (b[len].compareTo(top)<=0) {
len++;
//System.out.println(b[len]);
}
BigInteger res = BigInteger.ZERO;
for (int l=len;l>=0;l--){
if (n.compareTo( b[l].subtract(x1).multiply(m)) >0 ){
BigInteger tmp = n.divide(b[l]);
if (tmp.compareTo(m)>0) tmp=m;
n = n.subtract( tmp.multiply(b[l]) );
res = res.add(b[l]);
}
}
System.out.println(res);
}
}
}
zoj 3988(H) 题目要求 定义一个二元组(a,b):如果满足a+b为质数
参考AC代码 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
using namespace std;
int t,n,k,top;
int linker[maxn],a[maxn],prime[N+50];
bool used[maxn],p[N+50];
vector<int>g[maxn];
int vis[maxn];
void init
memset(p,0,sizeof(p));
top=0;
for (int i=2;i<=N;++i){
if (!p[i]) prime[++top]=i;
for (int j=1;j<=top;++j) {
if (i*prime[j]>N) break ;
p[i*prime[j]]=1;
if (i%prime[j]==0) break ;
}
}
}
bool dfs(int u){
used[u]=true ;
for (int i=0;i<(int)g[u].size();i++){
int next=g[u][i];
if (!used[next]){
used[next]=true ;
if (linker[next]==-1 || dfs(linker[next])){
linker[next]=u;
linker[u]=next;
return true ;
}
}
}
return false ;
}
int hungary
int ans=0;
mm(linker,-1);
for (int i=1;i<=n;i++){
if (vis[i] && linker[i]==-1){
mm(used,0);
if (dfs(i)) ans++;
}
}
return ans;
}
int main
// freopen("input.txt" ,"r" ,stdin);
init();
scanf("%d" ,&t);
while (t--){
scanf("%d%d" ,&n,&k);
for (int i=0;i<=n;i++) g[i].clear();
for (int i=1;i<=n;i++) scanf("%d" ,&a[i]);
mm(vis,0);
for (int i=1;i<=n;i++){
for (int j=i+1;j<=n;j++){
int temp=a[i]+a[j];
if (!p[temp]){
g[i].push_back(j);
g[j].push_back(i);
vis[i]=vis[j]=1;
}
}
}
int ans=hungary();
int cnt=0;
for (int i=1;i<=n;i++){
if (vis[i] && linker[i]==-1) cnt++;
}
if (ans>=k) printf ("%d\n" ,2*k);
else {
printf ("%d\n" ,2*ans+min(k-ans,cnt));
}
}
}
思路 二分图匹配
zoj 3992(L) 题目要求 有1-n n个字符 L表示往左走一格 R表示往右走一格 给出初始位置m 如果走到1位置或者n位置 游戏结束
参考AC代码 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
using namespace std;
int t,n,m;
char s[maxn];
int main
// freopen("input.txt" ,"r" ,stdin);
scanf("%d" ,&t);
while (t--){
scanf("%d%d" ,&n,&m);
scanf("%s" ,s+1);
int ans1=0,ans2=0;
if (s[m]=='L' ){
for (int i=m-1;i>1;i--){
if (s[i]=='R' ) ans1++;
}
ans2++;
for (int i=m+1;i<n;i++){
if (s[i]=='L' ) ans2++;
}
printf ("%d\n" ,min(ans1,ans2));
}
else {
for (int i=m+1;i<n;i++){
if (s[i]=='L' ) ans1++;
}
ans2++;
for (int i=m-1;i>1;i--){
if (s[i]=='R' ) ans2++;
}
printf ("%d\n" ,min(ans1,ans2));
}
}
return 0;
}
思路 模拟
