0.A - Simple Math 2
(
让我非常自闭的一道题,当时题还读反了,要求输出lfloor frac{10^N}{M}
floor\%M\
1<=N<=10^{18}\
1<=M<=10^4\
已知lfloor frac{lfloor frac{A}{B}
floor }{C}
floor = lfloor frac{A}{B*C}
floor
同理应该有lceil frac{lceil frac{A}{B}
ceil }{C}
ceil = lceil frac{A}{B*C}
ceil\
A\%B=A- lfloor frac{A}{B}
floor*B \
记Ans=lfloor frac{10^N}{M}
floor - lfloor frac{10^N}{M*M}
floor *M\
Q=lfloor frac{10^N}{M}
floor , Q^prime=lfloor frac{10^N}{M*M}
floor
由下取整得\
10^N = Q * M + R \
Q = frac {10^N - R}{M} \
10^N = Q^prime * M^2 + R^prime\
Q^prime = frac {10^N - R^prime}{M^2}
所以有：\
A = Q - Q^prime * M\
A = frac{(10^N - R) - (10^N - R^prime) }{M} =frac{R^prime-R}{M}\
=frac {(10^N\%M^2 - 10^N\%M)}{M}
总结就是%和下取整符号想办法化简掉就ok了
套个快速幂和龟速乘的板子就行了\
)
(
两行的python3标答离谱\
lfloor frac{10^N - kM^2}{M}
floor equiv lfloor frac{10^N}{M} - kM
floor equiv lfloor frac{10^N}{M}
floor - kM equiv lfloor frac{10^N}{M}
floor pmod M (k in mathbb{Z})
)
n, m = map(int, input().split())
print(pow(10, n, m * m) // m % m)
#include<iostream>
#include<algorithm>
using namespace std;
/*
ans= (10^N%(M^2)-10^N%M )/M
*/
typedef long long ll;
ll qmd(ll a,ll b,ll c);
ll qmi(ll a,ll b,ll c)
{
ll ans=1;
while(b)
{
if(b&1)
ans=qmd(ans,a,c)%c;
b>>=1;
a=qmd(a,a,c)%c;
}
return ans;
}
ll qmd(ll a,ll b,ll c)
{
//快速乘
ll ans=0;
while(b)
{
if(b&1)
ans=(ans+a)%c;
a=(a+a)%c;
b>>=1;
}
return ans;
}
int main()
{
ll n,m;cin>>n>>m;
cout<<(qmi(10,n,m*m)-qmi(10,n,m))/m;
return 0;
}
1.小希的迷宫
( 无向图判断是不是一棵树，坑点空图也是yes，自环是yes\ 只要判断这个无向图不存在一个节点有多个父亲，并且只\ 有唯一一个根(保证是连通图)即可 )
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
/*
并查集判有无环
*/
const int N=2e5+10;
bool flag=true;
int fa[N];
bool vis[N];
int find(int x)
{
if(x!=fa[x])
fa[x]=find(fa[x]);
return fa[x];
}
void merge(int x,int y)
{
vis[x]=vis[y]=1;
if(find(x)!=find(y))
fa[find(x)]=find(y);
else if(x!=y)//排除自环，有点坑
flag=false;
}
void init()
{
for(int i=1;i<=N;i++)
fa[i]=i;
for(int i=1;i<=N;i++)
vis[i]=0;
}
int main()
{
int n,m;
init();
while(cin>>n>>m,n!=-1&&m!=-1)
{
if(n==0&&m==0)//输入结束判断
{
bool nul=1;
for(int i=1;i<=N;i++)
if(vis[i])
nul=0;
if(nul)
{cout<<"Yes"<<endl;continue;}
if(!flag)
cout<<"No"<<endl;
else
{
int cnt=0;
// cout<<" "<<cnt<<endl;
for(int i=1;i<=N;i++)
if(vis[i]&&i==fa[i])
cnt++;
if(cnt==1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
init();
flag=true;
}
else
merge(n,m);
}
return 0;
}
2.Is It A Tree?
( 从无向图变成了有向图，1;2;3;2;0;0 是no，因为细节wa了很久，血炸 )
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
/*
并查集判有无环
*/
const int N=2e5+10;
bool flag=true;
int fa[N];
bool vis[N];
int find(int x)
{
if(x!=fa[x])
fa[x]=find(fa[x]);
return fa[x];
}
void merge(int x,int y)
{
vis[x]=vis[y]=1;
if(find(x)!=find(y))
fa[find(x)]=find(y);
else if(x!=y)//排除自环，有点坑
flag=false;
}
void init()
{
for(int i=1;i<=N;i++)
fa[i]=i;
for(int i=1;i<=N;i++)
vis[i]=0;
}
int main()
{
int n,m;
init();
while(cin>>n>>m,n!=-1&&m!=-1)
{
if(n==0&&m==0)//输入结束判断
{
bool nul=1;
for(int i=1;i<=N;i++)
if(vis[i])
nul=0;
if(nul)
{cout<<"Yes"<<endl;continue;}
if(!flag)
cout<<"No"<<endl;
else
{
int cnt=0;
// cout<<" "<<cnt<<endl;
for(int i=1;i<=N;i++)
if(vis[i]&&i==fa[i])
cnt++;
if(cnt==1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
init();
flag=true;
}
else
merge(n,m);
}
return 0;
}
3.B - Reversible Cards
思路A：
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
/*
判断这个无向图的每个连通块是否是树
*/
using namespace std;
/*
创建一个颜色图，并不断删除度为1的顶点。最终的答案是删除顶点的数目加上次数大于1的余数。
任何度等于1的顶点，只有一次被选择的机会。在对这些顶点进行重定时的过程结束时，度数大于1的顶点可以放入一个循环中，使它们被选中。
*/
#define INF 1000000000
#define MAXN 200010
#define MAXTAM 400010
int n;
int a[MAXN], b[MAXN];
vector<int> g[MAXTAM];
int deg[MAXTAM];
int main() {
scanf("%d", &n);
int i;
for (i=1; i<=n; i++) {
scanf("%d %d", &a[i], &b[i]);
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
deg[a[i]]++;
deg[b[i]]++;
}
queue<int> que;
for (i=0; i<MAXTAM; i++) {
if (deg[i]==1) {
que.push(i);
}
}
int ans = 0;
while (!que.empty()) {
int u = que.front();
que.pop();
if (deg[u]==1) {
// printf("**** %d
", u);
deg[u]--;
ans++;
for (i=0; i<g[u].size(); i++) {
int v = g[u][i];
deg[v]--;
if (deg[v]==1) {
que.pu sh(v);
}
}
}
}
for (i=0; i<MAXTAM; i++) {
if (deg[i]>=2) {
ans++;
}
}
printf("%d
", ans);
return 0;
}
思路B：
#include <bits/stdc++.h>
using namespace std;
int n,ans,a,b,fa[400050],t[400050];
int Fa(int x) {
if (fa[x]==x) return x;
return fa[x]=Fa(fa[x]);
}
int main() {
for (int i=1; i<=400000; ++i) fa[i]=i;
cin>>n;
while (n--) {
scanf("%d%d",&a,&b);
if (Fa(a)!=Fa(b)) {
if (t[Fa(a)]&&t[Fa(b)]) t[Fa(b)]=1;
else t[Fa(b)]+=t[Fa(a)],++ans;
fa[Fa(a)]=Fa(b);
} else if (!t[Fa(a)])
t[Fa(a)]=1,++ans;
}
cout<<ans;
}