2019 CCPC 秦皇岛

54 阅读 0 评论 36 点赞

我是靠谱客的博主故意手机，最近开发中收集的这篇文章主要介绍2019 CCPC 秦皇岛，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

A：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
struct node{
long long x,y;
node(long long x=0,long long y=0){
this->x = x;
this->y = y;
}
node base() const{
if (x < 0 || (x == 0 && y < 0)) return node(-x,-y);
return *this;
}
bool operator < (const node & rhs) const{
node p1 = base(),p2 = rhs.base();
return p1.x*p2.y < p1.y * p2.x;
}
node operator - (const node & rhs) const{
return node(x - rhs.x,y-rhs.y);
}
}a[N],que[N];
map<node, int> mp;
long long ans[N];
int main(){
int n,q;
while (scanf("%d%d",&n,&q) == 2) {
memset(ans, 0, sizeof(ans));
for(int i=0; i<n; i++){
scanf("%lld%lld",&a[i].x,&a[i].y);
}
for(int i=0; i<q; i++){
scanf("%lld%lld",&que[i].x,&que[i].y);
}
for(int i=0; i<q; i++){
mp.clear();
for(int j=0; j<n; j++){
mp[a[j] - que[i]]++;
}
for(int j=0; j<n; j++){
node p = a[j] - que[i];
p = node(-p.y,p.x);
ans[i] += mp.count(p) ? mp[p] : 0;
}
ans[i] /= 2;
}
for(int i=0; i<n; i++){
mp.clear();
for(int j=0; j<n; j++){
if (i != j){
mp[a[j] - a[i]]++;
}
}
for(int j=0; j<q; j++){
node p = que[j] - a[i];
p = node(-p.y,p.x);
ans[j] += mp.count(p) ? mp[p] : 0;
}
}
for(int i=0; i<q; i++){
printf("%lldn",ans[i]);
}
}
return 0;
}

D：暴力枚举10的倍数即可

#include <iostream>
using namespace std;
int main(){
int T;
scanf("%d",&T);
while(T--){
int n;
scanf("%d",&n);
long long res = 1;
int tag = 1;
for(res=1; res<(long long)1E18; res*=10){
if (res % n == 0) tag = 0;
}
if (tag) puts("Yes");
else puts("No");
}
return 0;
}

F: dfs搜出所有的环，统计答案即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
const long long mod = 998244353;
struct node{
int to,nex;
}ed[maxn << 1];
int head[maxn];
int num[maxn],stk[maxn],vis[maxn],in[maxn];
int idx,cur,tot,top = -1;
long long fac[maxn];
void add(int u,int v){
ed[++tot] = (node){v,head[u]};
head[u] = tot;
}
void dfs(int u,int fa){
stk[++top] = u;
vis[u] = 1;
in[u] = 1;
for(int i=head[u];i;i=ed[i].nex){
int v = ed[i].to;
if (!vis[v]){
dfs(v,u);
}else if (v != fa && in[v]){
int siz = 1,c = top;
while(1){
siz++;
c--;
if (stk[c] == v) break;
}
num[cur++] = siz;
}
}
in[stk[top]] = 0;
top--;
}
void init(){
memset(head,0,sizeof(head));
memset(ed, 0, sizeof(ed));
memset(vis,0,sizeof(vis));
memset(in,0,sizeof(in));
idx = cur = tot = 0;
top = -1;
}
int main(){
int n,m;
fac[0] = 1;
for(int i=1; i<maxn; i++){
fac[i] = fac[i-1] * 2 % mod;
}
while(scanf("%d%d",&n,&m) == 2){
init();
int u,v;
for(int i=1; i<=m; i++){
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
for(int i=1; i<=n; i++){
if (vis[i] == 0){
dfs(i,0);
}
}
int cnt = 0;
long long res = 1;
for(int i=0; i<cur; i++){
res = res * (fac[num[i]]-1) % mod;
cnt += num[i];
}
// cout << cnt << endl;
res = res * fac[m - cnt] % mod;
printf("%lldn",res);
}
return 0;
}

J : 倒着跑kmp然后枚举即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 10;
char s[maxn],a[maxn];
int nex[maxn];
void cal_nex(int len){
int k = 0;nex[0] = 0;
for(int i=1; i<len; i++){
while(a[i] != a[k] && k) k = nex[k-1];
if (a[i] == a[k]) k++;
nex[i] = k;
}
}
int main(){
long long n,m;
while (scanf("%lld%lld",&n,&m) == 2) {
scanf("%s",s);
int len = (int)strlen(s),lena = 0;
for(int i=0; i<len; i++){
if (s[len-i-1] == '.') break;
a[lena++] = s[len-i-1];
}
cal_nex(lena);
long long ans = -LLONG_MAX;
for(int i=0; i<lena; i++){
len = i + 1 - nex[i];
ans = max(ans,n*(i+1)-m*len);
}
printf("%lldn",ans);
}
return 0;
}

处理出每一个技能的6中状态转移到下一个技能的6种状态需要的最小次数然后dp即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int a[20][3] = {
{0,0,0},
{1,1,1},
{1,1,2},
{1,1,3},
{2,2,2},
{1,2,2},
{2,2,3},
{3,3,3},
{1,3,3},
{2,3,3},
{1,2,3}
};
int p[20][6][3];
int dis[20][20][6][6];
int dp[maxn][6];
char s[maxn];
int getid(char ch){
if (ch == 'Y') return 1;
if (ch == 'V') return 2;
if (ch == 'G') return 3;
if (ch == 'C') return 4;
if (ch == 'X') return 5;
if (ch == 'Z') return 6;
if (ch == 'T') return 7;
if (ch == 'F') return 8;
if (ch == 'D') return 9;
return 10;
}
int main(){
int b[3] = {0,1,2};
int cur = 0;
do{
for(int i=1; i<=10; i++){
p[i][cur][0] = a[i][b[0]];
p[i][cur][1] = a[i][b[1]];
p[i][cur][2] = a[i][b[2]];
}
cur++;
}while(next_permutation(b, b+3));
for(int i=1; i<=10; i++){
for(int j=1; j<=10; j++){
for(int ii=0; ii<6; ii++){
for(int jj=0; jj<6; jj++){
int len = 0;
if (p[i][ii][2] != p[j][jj][0]) len = 3;
if (p[i][ii][2] == p[j][jj][0]) len = 2;
if (p[i][ii][1] == p[j][jj][0] && p[i][ii][2] == p[j][jj][1]) len = 1;
if (p[i][ii][0] == p[j][jj][0] && p[i][ii][1] == p[j][jj][1] && p[i][ii][2] == p[j][jj][2]) len = 0;
dis[i][j][ii][jj] = len;
}
}
}
}
while(scanf("%s",s) == 1){
int len = (int)strlen(s);
for(int i=0; i<len; i++){
for(int j=0; j<6; j++){
dp[i][j] = inf;
}
}
for(int i=0; i<6; i++){
dp[0][i] = 3;
}
for(int i=1; i<len; i++){
int c1 = getid(s[i-1]),c2 = getid(s[i]);
for(int j=0; j<6; j++){
for(int k=0; k<6; k++){
dp[i][j] = min(dp[i][j],dp[i-1][k] + dis[c1][c2][k][j]);
}
}
}
int ans = inf;
for(int i=0; i<6; i++){
ans = min(ans,dp[len-1][i]);
}
printf("%dn",ans+len);
}
return 0;
}