D - M<=ab
题意：求最小的正整数，不小于 \(m\)，且能被表示为两个不大于 \(n\) 的正整数的数，不存在输出 -1。\(n,m\le10^{12}\)。
直接枚举 \(a\)，计算最小的满足 \(ab\ge m\) 的 \(b\)，如果 \(a>b\) 则后面的情况一定是重复的。时间复杂度 \(\text{O}(\sqrt n)\)。最好用 __int128 。
#include<bits/stdc++.h>
#define int __int128
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
inline void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10+'0');
}
signed main(){
int n=read(),m=read(),ans=n*n;
if(n*n<m)return puts("-1"),0;
for(int a=1;a<=n;a++){
int b=(m+a-1)/a;
if(b<=n&&a*b>=m)ans=min(ans,a*b);
if(b<a)break;
}
print(ans);
return 0;
}
E - Transition Game
题意：给一个 \(n\) 个点 \(n\) 条形如 \(i\rightarrow a_i\) 的有向边的图，求有多少个点在环中（包括自环）。\(n,a_i\le2\times10^5\)。
\(\text{tarjan}\) 缩点或者拓扑找环即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,inf=1e18;
inline int read(){
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
struct edge{
int v,nxt;
}e[N*2];
int head[N],tot;
void add(int u,int v){
e[++tot]=(edge){v,head[u]},head[u]=tot;
}
int dfn[N],low[N],in[N],a[N],val[N],col[N],rc,id;
stack<int>s;
void tarjan(int u){
dfn[u]=low[u]=++id;s.push(u);in[u]=1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
else if(in[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
int v;rc++;
do{v=s.top();s.pop();in[v]=0;col[v]=rc;val[rc]+=1;}while(u!=v);
}
}
int vis[N];
int u[N],v[N];
signed main(){
int n=read(),ans=0;
for(int i=1;i<=n;i++){
a[i]=read();
if(i!=a[i])add(i,a[i]);
else ans++;
}
for(int i=1;i<=n;i++){
if(!dfn[i])tarjan(i);
}
for(int i=1;i<=rc;i++){
if(val[i]>1)ans+=val[i];
}
printf("%lld\n",ans);
return 0;
}
F - Simultaneous Swap
题意：
G - Polygon and Points
题意：给定凸多边形，多次询问一个点在多边形内部/外部/边上。\(n,m\le2\times10^5\)。
计算几何板子，但我不会蒜几。