Codeforces 1068 - A/B/C/D/E - (Done)

链接:http://codeforces.com/contest/1068


A - Birthday - [计算题]

题意:一共 $N$ 种硬币,我已经有其中 $K$ 种,我的 $M$ 个朋友每人送我等数量的硬币,且送来的每一枚硬币都不属于同一种,要求最后我收到手上的硬币至少有 $L$ 种是我没有的,求每个人最少送几枚硬币。

题解:即求满足 $K + L \le aM \le N$ 的最小正整数 $a$。

AC代码:

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n,m,k,l;
int main()
{
cin>>n>>m>>k>>l;
if(m>n)
{
cout<<-<<endl;
return ;
}
if(k+l<=m)
{
cout<<<<endl;
return ;
}
ll a;
if((k+l)%m==) a=(k+l)/m;
else a=(k+l)/m+;
if(a*m>n) cout<<-<<endl;
else cout<<a<<endl;
}

B - LCM - [求因数个数]

题意:给定正整数 $b(b \le 10^{10})$,对于 $1 \le a \le 10^{18}$,求 $\frac{{{\mathop{\rm lcm}\nolimits} (a,b)}}{a}$ 的不同取值个数。

题解:$\frac{{{\mathop{\rm lcm}\nolimits} (a,b)}}{a} = \frac{{ab}}{{a\gcd (a,b)}} = \frac{b}{{\gcd (a,b)}}$,即求 $b$ 的因数个数。

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
int main()
{
cin>>n;
ll cnt=;
for(ll i=;i*i<=n;i++)
{
if(n%i==)
{
if(i*i==n) cnt++;
else cnt+=;
}
}
cout<<cnt<<endl;
}

C - Colored Rooks - [构造题]

题意:

给定一个 $10^9 \times 10^9$ 的正方形网格,现有 $n$ 种颜色,给若干个棋子上色(每种颜色都要涂至少一个棋子),又给出 $m$ 个颜色对 $(x,y)$ 表示这两个颜色是协调的

现在对于同一种颜色内的棋子集合,以及两个和谐的颜色对构成的棋子并集,都要满足连通性质,该性质的意思即:“首先规定棋子只可以走直线的任意距离,且可以完全不理睬非同集合内的棋子,但只有当它遇到同集合内的另一个棋子时才可以转弯。而该集合中任意一个棋子,都它可以走到集合内的任意其他棋子的位置。”

现在你要给出任意一种可行的放置棋子的方案。

题解:

首先,第 $i$ 行全部给第 $i$ 种颜色,不得放其他颜色。为了防止某种颜色没有涂棋子,可以先在 $(i,i)$ 位置放上颜色为 $i$ 的棋子。

然后对于给出的任意两个协调颜色,依次在后面的 $n+1, n+2, \cdots$ 列里放上对应行数的两枚棋子。

AC代码:

#include<bits/stdc++.h>
using namespace std; int n,m;
vector<int> ans[]; int main()
{
cin>>n>>m;
for(int i=;i<=n;i++) ans[i].push_back(i);
int col=n+;
for(int i=,u,v;i<=m;i++)
{
scanf("%d%d",&u,&v);
if(u==v) continue;
ans[u].push_back(col);
ans[v].push_back(col);
col++;
}
for(int i=;i<=n;i++)
{
printf("%d\n",ans[i].size());
for(int k=;k<ans[i].size();k++) printf("%d %d\n",i,ans[i][k]);
}
}

D - Array Without Local Maximums - [dp]

题意:给定一个长度为 $n(n \le 1e5)$ 的数组 $a[1:n]$,$a[i]$ 的值域为 $1$ 到 $200$,且每个数的旁边必须有一个不小于它的数。而有些数字被擦掉了,现在问共有多少种可行的填充方案。

题解:

看到这题第一感觉就dfs暴力搜索,然而时间复杂度显然不行,因此考虑dp。

考虑 $dp[i][x][0,1,2]$ 的表示的状态为已经确定了第 $i$ 个数字为 $x$,而 $0,1,2$ 分别表示第 $i-1$ 个数 $w$ 是小于、等于或大于 $x$。其存储的值是其状态下的方案数。

那么就有状态转移方程(当然这是建立在第 $i+1$ 位可以填 $y$ 的前提下的):

$\begin{array}{l} dp[i + 1][y][0] = \sum\limits_{x = 1}^{y - 1} {dp[i][x][0,1,2]} \\ dp[i + 1][y][1] = dp[i][y][0,1,2] \\ dp[i + 1][y][2] = \sum\limits_{x = y + 1}^{200} {dp[i][x][1,2]} \\ \end{array}$

边界条件,考虑到第 $1$ 个数左边是空的,相当于左边是一个更小的数,因此有(依然是建立在第一位能填入 $x$ 的前提下):

$\begin{array}{l} dp[1][x][0] = 1 \\ dp[1][x][1] = 0 \\ dp[1][x][2] = 0 \\ \end{array}$

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=;
const int maxn=1e5+;
int n,a[maxn];
ll sum,dp[maxn][][];
int main()
{
cin>>n;
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int x=;x<=;x++)
{
if(a[]!=- && a[]!=x) dp[][x][]=dp[][x][]=dp[][x][]=;
else dp[][x][]=, dp[][x][]=dp[][x][]=;
}
for(int i=;i<=n;i++)
{
sum=;
for(int y=;y<=;y++)
{
if(a[i]!=- && a[i]!=y) dp[i][y][]=;
else dp[i][y][]=sum;
sum+=(dp[i-][y][]+dp[i-][y][]+dp[i-][y][])%mod;
sum%=mod;
} for(int y=;y<=;y++)
{
if(a[i]!=- && a[i]!=y) dp[i][y][]=;
else dp[i][y][]=(dp[i-][y][]+dp[i-][y][]+dp[i-][y][])%mod;
} sum=;
for(int y=;y>=;y--)
{
if(a[i]!=- && a[i]!=y) dp[i][y][]=;
else dp[i][y][]=sum;
sum+=(dp[i-][y][]+dp[i-][y][])%mod;
sum%=mod;
}
}
ll ans=;
for(int x=;x<=;x++) ans+=(dp[n][x][]+dp[n][x][])%mod, ans%=mod;
cout<<ans<<endl;
}

E - Multihedgehog - [BFS]

题意:

一个连通无向图,若仅有一个节点度数不小于 $3$,其他所有节点度数均为 $1$,则称为“刺猬”。现在定义“$k$-刺猬”,为:

  “$1$-刺猬”即普通“刺猬”;

  对于“$k$-刺猬”,其由“$k-1$-刺猬”变化而来,将“$k-1$-刺猬”的所有度数为 $1$ 的顶点换成一个“$1$-刺猬”的中心,即构成“$k$-刺猬”。

现在给你一张图和一个 $k$,让你判断这张图是否为“$k$-刺猬”。

题解:

首先,当 $k=11$ 时,节点数最少也需要 ${\sum_{i=0}^{11}{3^i}} = 265720$ 个顶点,显然已经不够了,所以对于 $k \ge 11$ 的情况可以直接判断不行。

接下来,可以考虑以所有度数为零的节点为起始,将它们的深度定义为 $0$。然后自底向上地进行BFS(或者说BFS的一种变形?),同时不断地删除叶子结点。

对于每个节点,都需要判断它的深度和度数是否可行,还要判断其父亲节点是否只有一个。

对于最后一个没有父亲节点的根节点,判断他的深度是否等于 $k$。

AC代码:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+;
const int maxm=2e5+; int n,k;
int degree[maxn]; struct Edge{
int u,v;
int next;
};
Edge E[maxm];
int head[maxn],ne;
void init()
{
ne=;
memset(head,,sizeof(head));
}
void addedge(int u,int v)
{
++ne;
E[ne].u=u, E[ne].v=v;
E[ne].next=head[u];
head[u]=ne;
} int dist[maxn];
bool del[maxn],vis[maxn];
bool bfs()
{
queue<int> Q;
for(int i=;i<=n;i++)
{
if(degree[i]==) Q.push(i), vis[i]=, dist[i]=;
else vis[i]=;
}
memset(del,,sizeof(del));
while(!Q.empty())
{
int u=Q.front(); Q.pop();
del[u]=; //将节点删除 int cnt=; //记录父亲节点个数
for(int i=head[u];i;i=E[i].next)
{
int v=E[i].v; if(del[v]) continue;
else cnt++;
if(cnt>) return false; //父亲节点应当只有一个 if(!vis[v])
{
vis[v]=;
dist[v]=dist[u]+;
Q.push(v);
}
else
{
if(dist[v]!=dist[u]+) return false;
}
} if(cnt==) { //当前节点是根节点
if(degree[u]<) return false;
if(dist[u]!=k) return false;
}
else if(degree[u]>) { //当前节点不是根节点也不是叶子结点
if(degree[u]<=) return false;
}
}
return true;
} int main()
{
cin>>n>>k;
init();
memset(degree,,sizeof(degree));
for(int i=,u,v;i<n;i++)
{
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
degree[u]++;
degree[v]++;
}
if(n< || k>=) printf("No\n");
else printf("%s\n",bfs()?"Yes":"No");
}
上一篇:python 模拟豆瓣登录(豆瓣6.0)


下一篇:从0开始学golang--2.1--如何去爬园子的数据