CF1036A Function Height
答案为 \(\lceil \frac{k}{n}\rceil\)。
#include<iostream>
#include<cstdio>
using namespace std;
long long n,k;
int main()
{
scanf("%lld%lld",&n,&k);
printf("%lld",(k+n-1)/n);
return 0;
}
CF1036B Diagonal Walking v.2
不妨令 \(n\le m\)。
可以发现，对于行最多只有 \(1\) 步不走斜步，对于列最多只有 \(1\) 步不走斜步，判断一下是否走这一步即可。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int T;
long long n,m,k;
void solve()
{
scanf("%lld%lld%lld",&n,&m,&k);
if(n<0) n=-n;
if(m<0) m=-m;
if(n>m) swap(n,m);
if(k<m) printf("-1\n");
else printf("%lld\n",k-(k-n)%2-(k-m)%2);
return;
}
int main()
{
scanf("%d",&T);
while(T--)
solve();
return 0;
}
CF1036C Classy Numbers
令 \(f_{i,j,0/1}\) 表示当前到第 \(i\) 位，还有 \(j\) 个 \(1\sim 9\) 可以放，是否卡上界，直接数位 DP 就完了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=20;
int s[N],tot;
long long f[N][4][2];
long long dfs(int now,int ret,bool flag)
{
if(ret<0) return 0;
if(now==0) return 1;
if(f[now][ret][flag]!=-1) return f[now][ret][flag];
long long res=0;
for(int i=0;i<=9;i++)
if(!flag||(flag&&i<=s[now])) res+=dfs(now-1,ret-(i!=0),flag&&s[now]==i);
return f[now][ret][flag]=res;
}
long long calc(long long x)
{
if(x==0) return 1;
tot=0;
while(x) s[++tot]=x%10,x/=10;
memset(f,-1,sizeof(f));
return dfs(tot,3,true);
}
int T;
long long l,r;
void dfs()
{
scanf("%lld%lld",&l,&r);
printf("%lld\n",calc(r)-calc(l-1));
return;
}
int main()
{
scanf("%d",&T);
while(T--)
dfs();
return 0;
}
CF1036D Vasya and Arrays
\(a,b\) 的每个分界点的前缀和对应相等。令 \(sa,sb\) 表示 \(a,b\) 的前缀和。如果 \(sa_i=sb_j\)，我们肯定可以可以原来的基础上加一个 \(i,j\) 作为分界点。\(sa,sb\) 具有单调性，双指针扫一扫即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=300005;
int n,m;
int a[N],b[N];
long long sa[N],sb[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++)
scanf("%d",&b[i]);
for(int i=1;i<=n;i++)
sa[i]=sa[i-1]+a[i];
for(int i=1;i<=m;i++)
sb[i]=sb[i-1]+b[i];
int ans=0;
for(int i=1,j=1;i<=n;i++)
{
while(j<=m&&sb[j]<sa[i]) j++;
if(sb[j]==sa[i]) ans++;
}
if(sa[n]!=sb[m])
{
printf("-1");
return 0;
}
printf("%d",ans);
return 0;
}
CF1036E Covered Points
一条线上的整点个数为：
\[\gcd(|x_1-x_2|,|y_1-y_2|)+1 \]先将一条线上不在其他线上的点算上，然后在加上在多条线段上的点即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<set>
#include<algorithm>
using namespace std;
const int N=1005;
const double eps=1e-12;
struct Point
{
double x,y;
Point(double _x=0,double _y=0)
{
x=_x,y=_y;
return;
}
Point operator+(const Point &rhs)const
{
return {x+rhs.x,y+rhs.y};
}
Point operator-(const Point &rhs)const
{
return {x-rhs.x,y-rhs.y};
}
Point operator*(const double &rhs)const
{
return {x*rhs,y*rhs};
}
Point operator/(const double &rhs)const
{
return {x/rhs,y/rhs};
}
bool operator<(const Point &rhs)const
{
return x<rhs.x||(x==rhs.x&&y<rhs.y);
}
bool operator==(const Point &rhs)const
{
return x==rhs.x&&y==rhs.y;
}
friend double cross(const Point &a,const Point &b)
{
return a.x*b.y-a.y*b.x;
}
};
struct Line
{
Point a,b;
friend bool segment_intersection(const Line &a,const Line &b)
{
double t1=cross(b.a-a.a,a.b-a.a),t2=cross(b.b-a.a,a.b-a.a);
if((t1>0&&t2>0)||(t1<0&&t2<0)) return false;
t1=cross(a.a-b.a,b.b-b.a),t2=cross(a.b-b.a,b.b-b.a);
if((t1>0&&t2>0)||(t1<0&&t2<0)) return false;
return true;
}
friend Point cross_point(const Line &a,const Line &b)
{
Point u=a.a-b.a,v=a.b-a.a,w=b.b-b.a;
return a.a+v*cross(w,u)/cross(v,w);
}
};
int n;
Line a[N];
set<Point>S;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf%lf%lf",&a[i].a.x,&a[i].a.y,&a[i].b.x,&a[i].b.y);
long long ans=0;
for(int i=1;i<=n;i++)
{
set<Point>t;
for(int j=1;j<=n;j++)
if(i!=j)
if(segment_intersection(a[i],a[j]))
{
Point p=cross_point(a[i],a[j]);
if(abs(p.x-floor(p.x))<eps&&abs(p.y-floor(p.y))<eps)
{
S.insert(p);
t.insert(p);
}
}
ans+=abs(__gcd((long long)(a[i].b.x-a[i].a.x),(long long)(a[i].b.y-a[i].a.y)))+1-t.size();
}
ans+=S.size();
printf("%lld",ans);
return 0;
}
CF1036F Relatively Prime Powers
考虑计算不合法的个数，如果不合法数一定可以表示成某个数 \(x\) 的次幂的形式，即 \(x^k\)（\(k\ge 2\)）。
对于 \(k=2\) 的情况直接开方，\(k\ge 3\) 的情况预处理即可。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1000005;
const long long INF=1e18;
int T;
long long val[N*10];
int tot;
long long mul(long long a,long long b)
{
__int128 c=(__int128)a*b;
if(c>INF) return INF+1;
else return c;
}
void init(int n=1000000)
{
for(int i=2;i<=n;i++)
{
long long p=1LL*i*i*i;
while(p<=INF)
{
auto check=[=](long long x)
{
long long t=(long long)sqrt(x);
while(t*t<x) t++;
while(t*t>x) t--;
return t*t!=x;
};
if(check(p)) val[++tot]=p;
p=mul(p,i);
}
}
sort(val+1,val+tot+1);
tot=unique(val+1,val+tot+1)-val-1;
return;
}
long long n;
void solve()
{
scanf("%lld",&n);
long long t=sqrt(n);
while(t*t<n) t++;
while(t*t>n) t--;
long long ans=(n-(upper_bound(val+1,val+tot+1,n)-val-1)-t);
printf("%lld\n",ans);
return;
}
int main()
{
init();
scanf("%d",&T);
while(T--)
solve();
return 0;
}
CF1036G Sources and Sinks
对于一个源点点集 \(S\)，如果它的汇点个数小于等于源点个数一定不合法，因为我们可以将所有的汇点连到源点上就好了。
枚举点集计算即可，需要预处理每个源点能到的汇点集合。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1000005;
const long long INF=1e18;
int T;
long long val[N*10];
int tot;
long long mul(long long a,long long b)
{
__int128 c=(__int128)a*b;
if(c>INF) return INF+1;
else return c;
}
void init(int n=1000000)
{
for(int i=2;i<=n;i++)
{
long long p=1LL*i*i*i;
while(p<=INF)
{
auto check=[=](long long x)
{
long long t=(long long)sqrt(x);
while(t*t<x) t++;
while(t*t>x) t--;
return t*t!=x;
};
if(check(p)) val[++tot]=p;
p=mul(p,i);
}
}
sort(val+1,val+tot+1);
tot=unique(val+1,val+tot+1)-val-1;
return;
}
long long n;
void solve()
{
scanf("%lld",&n);
long long t=sqrt(n);
while(t*t<n) t++;
while(t*t>n) t--;
long long ans=(n-(upper_bound(val+1,val+tot+1,n)-val-1)-t);
printf("%lld\n",ans);
return;
}
int main()
{
init();
scanf("%d",&T);
while(T--)
solve();
return 0;
}