2019 CCPC 秦皇岛站

125 阅读 0 评论 83 点赞

我是靠谱客的博主曾经爆米花，这篇文章主要介绍2019 CCPC 秦皇岛站，现在分享给大家，希望可以做个参考。

题目链接

排名：95 / 265 35.85%

国庆出去玩了，昨天晚上到的学校，现在把走之前做的题总结一下。

HDU 6734 Decimal

题意：让你算1/n是不是无限小数。

思路：只需要判断n是不是2或者5的倍数就行了。

复制代码

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
#include <bits/stdc++.h>
using namespace std;
bool judge(int n)
{
if(n == 1) return true;
if(n == 2 || n == 5) return true;
if(n % 2 == 0)
{
while(n % 2 == 0)
n /= 2;
}
if(n %5 == 0)
{
while(n % 5 == 0)
n /= 5;
}
if(n == 1) return true;
return false;
}
int main()
{
int T;scanf("%d", &T);
while(T --)
{
int n;
scanf("%d", &n);
if(judge(n))
printf("Non");
else
printf("Yesn");
}
return 0;
}

HDU 6736 Forest Program

题意：给你一个含有n个点和m条边的无向连通图，问存在多少种移除情况使得移除某些边之后剩下的图的所有块都是树。题目还想保证了输入的图一定含有环。

思路：搜索这个图，设图中第i个环含有的边数为mi（不在环中的边有m0条），则最后的答案是2^m0+2^m1-1+2^m2-1+...。所以只需要dfs标记统计一下每个环的边数就行了，标记的时候不能标记点，要标记边。

复制代码

#include<bits/stdc++.h>
#define mem(a,b) memset((a),b,sizeof(a))
#define de cout<<endl<<endl<<endl
typedef long long ll;
const int inf=0x3f3f3f3f;
const int N=600010;
const int M=1000010;
const ll mod=998244353;
using namespace std;
int n,m,tot,head[N],ver[M],Next[M],v[N];
ll ans=1;
int mm;
set<int> s[N];
ll pow_mod(ll a,ll b)
{
ll ret=1;
while(b)
{
if(b&1) ret=ret*a%mod;
b>>=1;
a=a*a%mod;
}
return ret;
}
void add(int x,int y)
{
ver[++tot]=y;Next[tot]=head[x];head[x]=tot;
}
void init()
{
tot=0;
mm=0;
ans=1;
for(int i=0;i<=n;i++)
head[i]=0,s[i].clear(),v[i]=0;
}
void dfs(int x)
{
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(s[x].find(y)!=s[x].end())
continue;
s[x].insert(y);
s[y].insert(x);
if(v[y]!=0)
{
ans=ans*((pow_mod(2,v[x]-v[y]+1)-1)%mod)%mod;
mm+=v[x]-v[y]+1;
}
else
{
v[y]=v[x]+1;
dfs(y);
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
int x,y;
for(int i=1;i<=m;i++)
{scanf("%d%d",&x,&y);add(x,y);add(y,x);}
v[1]=1;
dfs(1);
ans=ans*pow_mod(2,1ll*(m-mm))%mod;
printf("%lldn",ans);
init();
}
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
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
#include<bits/stdc++.h>
#define mem(a,b) memset((a),b,sizeof(a))
#define de cout<<endl<<endl<<endl
typedef long long ll;
const int inf=0x3f3f3f3f;
const int N=600010;
const int M=1000010;
const ll mod=998244353;
using namespace std;
int n,m,tot,head[N],ver[M],Next[M],v[N];
ll ans=1;
int mm;
set<int> s[N];
ll pow_mod(ll a,ll b)
{
ll ret=1;
while(b)
{
if(b&1) ret=ret*a%mod;
b>>=1;
a=a*a%mod;
}
return ret;
}
void add(int x,int y)
{
ver[++tot]=y;Next[tot]=head[x];head[x]=tot;
}
void init()
{
tot=0;
mm=0;
ans=1;
for(int i=0;i<=n;i++)
head[i]=0,s[i].clear(),v[i]=0;
}
void dfs(int x)
{
for(int i=head[x];i;i=Next[i])
{
int y=ver[i];
if(s[x].find(y)!=s[x].end())
continue;
s[x].insert(y);
s[y].insert(x);
if(v[y]!=0)
{
ans=ans*((pow_mod(2,v[x]-v[y]+1)-1)%mod)%mod;
mm+=v[x]-v[y]+1;
}
else
{
v[y]=v[x]+1;
dfs(y);
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
int x,y;
for(int i=1;i<=m;i++)
{scanf("%d%d",&x,&y);add(x,y);add(y,x);}
v[1]=1;
dfs(1);
ans=ans*pow_mod(2,1ll*(m-mm))%mod;
printf("%lldn",ans);
init();
}
return 0;
}

HDU 6739 Invoker

题意：一个人口袋里最多能装三张字母牌，输入一个字符串，字符串中的每个字符都对应着三个字母牌（这三个字母牌是无序的），问遍历这个字符串，需要往口袋里放置多少次字母牌，遍历到某个字符是都要在口袋里搞到该字符对应的字母牌，如果口袋里的牌多于3张，就要移除最早装进口袋的那张牌，并且没遍历一个字符就要加上一个'R'。

思路：如果题意搞明白了，这个dp一下就行了，dp的时候注意细节。

复制代码

#include<bits/stdc++.h>
#define mem(a,b) memset((a),b,sizeof(a))
#define de cout<<endl<<endl<<endl
typedef long long ll;
const int inf=500000;
using namespace std;
char a[100010];
int dp[100010][30];
int cnt1[4],cnt2[4];
int G[30]={0,111,112,113,121,122,123,131,132,133,211,212,213,221,222,223,231,232,233,311,312,313,321,322,323,331,332,333};
int get(int a,int b)
{
//QWE
int p1,p2,p3;
int p=G[a];
p1=p%10;p2=p/10%10;p3=p/100%10;
int q1,q2,q3;
int q=G[b];
q1=q%10;q2=q/10%10;q3=q/100%10;
if(p1==q1&&p2==q2&&p3==q3)
return 0;
if(p2==q1&&p3==q2)
return 1;
if(p3==q1)
return 2;
return 3;
}
bool ok(int a,char c)
{
//QWE
int p1,p2,p3;
int p=G[a];
p1=p%10;p2=p/10%10;p3=p/100%10;
int q1,q2,q3;
if(c=='Y')
{q1=1;q2=1;q3=1;}
if(c=='V')
{q1=1;q2=1;q3=2;}
if(c=='G')
{q1=1;q2=1;q3=3;}
if(c=='C')
{q1=2;q2=2;q3=2;}
if(c=='X')
{q1=1;q2=2;q3=2;}
if(c=='Z')
{q1=2;q2=2;q3=3;}
if(c=='T')
{q1=3;q2=3;q3=3;}
if(c=='F')
{q1=1;q2=3;q3=3;}
if(c=='D')
{q1=2;q2=3;q3=3;}
if(c=='B')
{q1=1;q2=2;q3=3;}
mem(cnt1,0);mem(cnt2,0);
cnt1[p1]++;cnt1[p2]++;cnt1[p3]++;
cnt2[q1]++;cnt2[q2]++;cnt2[q3]++;
if(cnt1[1]==cnt2[1]&&cnt1[2]==cnt2[2]&&cnt1[3]==cnt2[3])
return true;
return false;
}
int main()
{
while(scanf("%s",a+1)!=EOF)
{
int n=strlen(a+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=27;j++)
dp[i][j]=inf;
for(int i=1;i<=27;i++)
if(ok(i,a[1]))
dp[1][i]=3;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=27;j++)
{
if(!ok(j,a[i]))
continue;
for(int k=1;k<=27;k++)
{
if(!ok(k,a[i-1]))
continue;
dp[i][j]=min(dp[i][j],dp[i-1][k]+get(k,j));
}
}
}
int ans=inf;
for(int i=1;i<=27;i++)
if(ok(i,a[n]))
ans=min(ans,dp[n][i]);
ans+=n;
printf("%dn",ans);
}
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
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<bits/stdc++.h>
#define mem(a,b) memset((a),b,sizeof(a))
#define de cout<<endl<<endl<<endl
typedef long long ll;
const int inf=500000;
using namespace std;
char a[100010];
int dp[100010][30];
int cnt1[4],cnt2[4];
int G[30]={0,111,112,113,121,122,123,131,132,133,211,212,213,221,222,223,231,232,233,311,312,313,321,322,323,331,332,333};
int get(int a,int b)
{
//QWE
int p1,p2,p3;
int p=G[a];
p1=p%10;p2=p/10%10;p3=p/100%10;
int q1,q2,q3;
int q=G[b];
q1=q%10;q2=q/10%10;q3=q/100%10;
if(p1==q1&&p2==q2&&p3==q3)
return 0;
if(p2==q1&&p3==q2)
return 1;
if(p3==q1)
return 2;
return 3;
}
bool ok(int a,char c)
{
//QWE
int p1,p2,p3;
int p=G[a];
p1=p%10;p2=p/10%10;p3=p/100%10;
int q1,q2,q3;
if(c=='Y')
{q1=1;q2=1;q3=1;}
if(c=='V')
{q1=1;q2=1;q3=2;}
if(c=='G')
{q1=1;q2=1;q3=3;}
if(c=='C')
{q1=2;q2=2;q3=2;}
if(c=='X')
{q1=1;q2=2;q3=2;}
if(c=='Z')
{q1=2;q2=2;q3=3;}
if(c=='T')
{q1=3;q2=3;q3=3;}
if(c=='F')
{q1=1;q2=3;q3=3;}
if(c=='D')
{q1=2;q2=3;q3=3;}
if(c=='B')
{q1=1;q2=2;q3=3;}
mem(cnt1,0);mem(cnt2,0);
cnt1[p1]++;cnt1[p2]++;cnt1[p3]++;
cnt2[q1]++;cnt2[q2]++;cnt2[q3]++;
if(cnt1[1]==cnt2[1]&&cnt1[2]==cnt2[2]&&cnt1[3]==cnt2[3])
return true;
return false;
}
int main()
{
while(scanf("%s",a+1)!=EOF)
{
int n=strlen(a+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=27;j++)
dp[i][j]=inf;
for(int i=1;i<=27;i++)
if(ok(i,a[1]))
dp[1][i]=3;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=27;j++)
{
if(!ok(j,a[i]))
continue;
for(int k=1;k<=27;k++)
{
if(!ok(k,a[i-1]))
continue;
dp[i][j]=min(dp[i][j],dp[i-1][k]+get(k,j));
}
}
}
int ans=inf;
for(int i=1;i<=27;i++)
if(ok(i,a[n]))
ans=min(ans,dp[n][i]);
ans+=n;
printf("%dn",ans);
}
return 0;
}