AtCoder Beginner Contest 293(C,D ,E,F)
C
这道题其实还蛮好写的，就是一个\(dfs\),然后我看错了题意，就记录一下
这道题的大意是我们需要从\((1,1)\)走到\((n,m)\),我们只有两种走法，向下走和向右走，然后对于这一条路上存在有两个位置上的数是一样的，那么我们就认为这一条路是不高兴的，问我们从\((1,1)\)走到\((n,m)\)高兴的路有多少条
题意理解清楚了就很好办
对于判断是否高兴，我们可以用到回溯
然后又看到\(n\)和\(m\)都不是很大，那么我们就可以直接\(dfs\)了
#include <iostream>
#include <string>
#include <vector>
#include <map>
using namespace std;
#define int long long
const int maxn=2e5+10;
int n,m;
int a[20][20];
map<int,bool>vis;
int ans;
void dfs(int x,int y)
{
if(x==n&&y==m)
{
ans++;
return ;
}
int sum=0;
if(x<n)
{
if(!vis[a[x+1][y]])
{
vis[a[x+1][y]]=true;
dfs(x+1,y);
vis[a[x+1][y]]=false;
}
}
if(y<m)
{
if(!vis[a[x][y+1]])
{
vis[a[x][y+1]]=true;
dfs(x,y+1);
vis[a[x][y+1]]=false;
}
}
return ;
}
signed main ()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
vis[a[1][1]]=true;
ans=0;
dfs(1,1);
cout<<ans<<'\n';
system ("pause");
return 0;
}
D
我一看这题就迷糊
什么颜色，什么捆绑，讲的迷迷糊糊的，看的我太气愤了
然后看了佬们的题解才真正的看懂这个题意
其实这个题目有一个干扰条件，就是那个颜色
我们在做题的时候可以不用管那个颜色，然后会有\(m\)次捆绑两条绳子，问最后有多少个绳子集合是有环的，有多少个绳子集合是无环的
对于捆绑合并这一类的问题，我们可以用并查集
然后对于这一个集合，怎样判断这一个集合里面是否存在环呢
我们可以想到对于\(n\)个点，要使这\(n\)个点没有环并且边最多的时候边的数量为\(n-1\)条
那么对于存在\(cnt\)个点的集合，如果这\(cnt\)个点里面的边的数量大于等于点的数量，那么就说明这个集合一定有环，否则无环
#include <iostream>
#include <string>
using namespace std;
const int maxn=2e5+10;
int f[maxn],siz[maxn],d[maxn];
int n,m;
int find(int x)
{
if(x==f[x]) return x;
return f[x]=find(f[x]);
}
void merge(int x,int y)
{
int tx=find(x);
int ty=find(y);
if(tx==ty) return ;
f[ty]=tx;
siz[tx]+=siz[ty];
d[tx]+=d[ty];
siz[ty]=0;
}
int main ()
{
cin>>n>>m;
for (int i=1;i<=n;i++)//记得要初始化
{
f[i]=i;
siz[i]=1,d[i]=0;
}
for (int i=1;i<=m;i++)
{
char ch1,ch2;
int u,v;
cin>>u>>ch1>>v>>ch2;
merge(u,v);
d[find(u)]++;//还要记u,v之间还有一条边是连接这两个点的
}
int cnt1=0,cnt2=0;
for (int i=1;i<=n;i++)
{
if (i==find(i))
{
if(d[i]>=siz[i])
{
cnt1++;
}
else cnt2++;
}
}
cout<<cnt1<<" "<<cnt2<<"\n";
system ("pause");
return 0;
}
E
我们要求以下式子的和
\[\sum_{i=0}^{x-1} a^i \]那么我们就可以把这些看成是一个等比公式，公比是\(a\)
可以变化成
\[a^0+a^1+a^2+...+a^{x-2}+a^{x-1} \]那么我们对于这一个式子，我们还可以进行以下两种变换
如果\(x\)是一个偶数，那么就相当于这一个式子可以分成两部分
如下
\[\sum_{i=0}^{x-1}a^i=(a^0+a^1+...a^{ \frac{x}{2}-1})+a^{ \frac{x}{2}}\times (a^0+a^1+...a^{ \frac{x}{2}-1}) \]而如果\(x\)是一个奇数，那么可以进行以下变换
\[\sum_{i=0}^{x-1}a^i=a^0+a\times (a^0+a^1+a^2+...+a^{x-2}) \]我们可以发现，\(x\)不管是奇数还是偶数，都会进入下一个更小的求和，所以我们就可以发现其中的规律
然后我们就可以推断出递推的公式了
int get(int x)
{
if(x==1) return 1;
if(x&1)
{
return ((1+a*get(x-1)%mod)%mod);
}
else
{
return (((ksm(a,x/2)+1)%mod*get(x/2))%mod);
}
}
具体操作就看代码
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
int mod;
int a,x;
int ksm(int x,int p)
{
int res=1;
while (p)
{
if(p&1)
{
res=(res*x)%mod;
}
x=(x*x)%mod;
p>>=1;
}
return res%mod;
}
int get(int x)
{
if(x==1) return 1;
if(x&1)
{
return ((1+a*get(x-1)%mod)%mod);
}
else
{
return (((ksm(a,x/2)+1)%mod*get(x/2))%mod);
}
}
signed main ()
{
cin>>a>>x>>mod;
int ans=get(x);
ans%=mod;
cout<<ans<<'\n';
system ("pause");
return 0;
}
F
这个题意虽然一开始没看懂，但最后还是看懂了
大意就是给你一个数\(n\),问有多少种进制可以表示出\(n\)
如\(6\)用\(2\)进制可以是\(110\),用\(5\)进制可以是\(11\)这种的表达形式
我们可以知道这个进制一定是小于等于\(n\)里面寻找的
然后我们可以注意到这个\(n\)非常的大，那么我们可以分成两部分
对于小于等于\(1000\)的我们可以直接判断
对于怎么判断一个数是否可以用这样的进制表达
我们是这样子判断的
bool check(int x)
{
int now=n;
while (now)
{
if(now%x>1) return false;
now/=x;
}
return true;
}
对于大于\(1000\)的，要到达\(1e18\),最多就是\(6\)位，这就以为着这里面的形式（1100这种的）不是很多，我们可以考虑列举出这些形式，找到一个合适的进制，看是否可以得到\(n\)
对于每一种形式怎么找到一个合适的进制呢
我们可以用二分来查找
__int128 calc(int bit,int v)//这里用到了__int128,用long long 可能不够
{
__int128 s=0,pw=1;
for (int j=0;j<7;j++)
{
if(bit>>j&1)
{
if(pw>n) return 9e18;
else
{
s+=pw;
}
}
if(s>n) return 9e18;
if(pw<2e18)
{
pw*=v;
}
}
return s;
}
我觉得这道题比较好的点就是他对于一个很大的数，它对于那些可能进制数很大的它不是一个一个直接判断，而是通过我们还可以存在的形式来找那些进制（最多只有\(2^7-1\)个）
然后这个题还要注意数据的范围，有些地方可能会超过\(long\) \(long\)
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
#define int long long
int t,n;
bool check(int x)
{
int now=n;
while (now)
{
if(now%x>1) return false;
now/=x;
}
return true;
}
__int128 calc(int bit,int v)
{
__int128 s=0,pw=1;
for (int j=0;j<7;j++)
{
if(bit>>j&1)
{
if(pw>n) return 9e18;
else
{
s+=pw;
}
}
if(s>n) return 9e18;
if(pw<2e18)
{
pw*=v;
}
}
return s;
}
bool binarysearch(int bit)
{
__int128 l=1001,r=2e18;
__int128 ans;
while (l<=r)
{
__int128 mid=(l+r)>>1;
if(calc(bit,mid)<=n)
{
ans=mid;
l=mid+1;
}
else r=mid-1;
}
if(calc(bit,ans)==n) return true;
else return false;
}
void solve()
{
cin>>n;
int ans=0;
for (int i=2;i<=min(n,1000*1ll);i++)
{
ans+=check(i);
}
if(n>1000)
{
for (int state=1;state<(1<<7);state++)
{
ans+=binarysearch(state);
}
}
cout<<ans<<'\n';
return ;
}
signed main ()
{
cin>>t;
while (t--)
{
solve();
}
system ("pause");
return 0;
}