A - N-choice question
太简单，直接放代码：
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define gt getchar
#define pt putchar
#define y1 y233
//typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 lll;
//typedef __uint128_t ulll;
using namespace std;
inline bool __(char ch){return ch>=48&&ch<=57;}
inline int read(){
int x=0;bool sgn=0;char ch=gt();
while(!__(ch)&&ch!=EOF){sgn|=(ch=='-');ch=gt();}
while(__(ch)){x=(x<<1)+(x<<3)+(ch-48);ch=gt();}
return sgn?-x:x;
}
template<class T>
inline void print(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);
}
template<class T>
inline void printsp(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(32);
}
template<class T>
inline void println(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(10);
}
inline void put_str(string s){
int siz=s.size();
for(int i=0;i<siz;++i) pt(s[i]);
printf("\n");
}
int n,a,b,c[305];
signed main(){
n=read(),a=read(),b=read();
for(int i=1;i<=n;++i){
c[i]=read();
if(a+b==c[i]){
println(i);
return 0;
}
}
return 0;
}
B - Same Map in the RPG World
第一眼看上去好像没那么好做。但是会发现右移 \(h\) 次、下移 \(w\) 次就会回到原矩阵。所以暴力枚举右移和下移的次数即可。
时间复杂度 \(O(n^5)\)，可以通过。
代码：
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define gt getchar
#define pt putchar
#define y1 y233
//typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 lll;
//typedef __uint128_t ulll;
using namespace std;
inline bool __(char ch){return ch>=48&&ch<=57;}
inline int read(){
int x=0;bool sgn=0;char ch=gt();
while(!__(ch)&&ch!=EOF){sgn|=(ch=='-');ch=gt();}
while(__(ch)){x=(x<<1)+(x<<3)+(ch-48);ch=gt();}
return sgn?-x:x;
}
template<class T>
inline void print(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);
}
template<class T>
inline void printsp(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(32);
}
template<class T>
inline void println(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(10);
}
inline void put_str(string s){
int siz=s.size();
for(int i=0;i<siz;++i) pt(s[i]);
printf("\n");
}
int n,m;
char s[35][35],t[35][35],g[35],tmp[35][35];
inline void move(int x,int y){
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) tmp[i][j]=s[i][j];
for(int cnt=1;cnt<=x;++cnt){
for(int j=1;j<=m;++j) g[j]=tmp[1][j];
for(int i=1;i<n;++i) for(int j=1;j<=m;++j) tmp[i][j]=tmp[i+1][j];
for(int j=1;j<=m;++j) tmp[n][j]=g[j];
}
for(int cnt=1;cnt<=y;++cnt){
for(int i=1;i<=n;++i) g[i]=tmp[i][1];
for(int i=1;i<=n;++i) for(int j=1;j<m;++j) tmp[i][j]=tmp[i][j+1];
for(int i=1;i<=n;++i) tmp[i][m]=g[i];
}
}
inline bool same(char a[35][35],char b[35][35]){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(a[i][j]!=b[i][j]) return 0;
}
}
return 1;
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
for(int i=1;i<=n;++i) scanf("%s",t[i]+1);
for(int x=1;x<=n;++x){
for(int y=1;y<=m;++y){
move(x,y);
if(same(tmp,t)){
printf("Yes\n");
return 0;
}
}
}
printf("No\n");
return 0;
}
C - Cross
没难度。
首先注意到 \((x,y)\) 最多也只能构成长为 $\min(x-1,n-x,y-1,m-y) $ 的十字架，因此先判断当前位置是否为 #，然后直接枚举长度，用桶计数即可。
代码：
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define gt getchar
#define pt putchar
#define y1 y233
//typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 lll;
//typedef __uint128_t ulll;
using namespace std;
inline bool __(char ch){return ch>=48&&ch<=57;}
inline int read(){
int x=0;bool sgn=0;char ch=gt();
while(!__(ch)&&ch!=EOF){sgn|=(ch=='-');ch=gt();}
while(__(ch)){x=(x<<1)+(x<<3)+(ch-48);ch=gt();}
return sgn?-x:x;
}
template<class T>
inline void print(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);
}
template<class T>
inline void printsp(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(32);
}
template<class T>
inline void println(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(10);
}
inline void put_str(string s){
int siz=s.size();
for(int i=0;i<siz;++i) pt(s[i]);
printf("\n");
}
int n,m,cnt[105];
char s[105][105];
inline int calc(int x,int y){
int ans=0,limit=min(x-1,min(n-x,min(y-1,m-y)));
if(s[x][y]=='.') return 0;
for(int i=1;i<=limit;++i){
if(s[x+i][y+i]=='.'||s[x+i][y-i]=='.'||s[x-i][y+i]=='.'||s[x-i][y-i]=='.') break;
ans++;
}
return ans;
}
signed main(){
n=read(),m=read();
for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cnt[calc(i,j)]++;
for(int i=1;i<=min(n,m);++i) printsp(cnt[i]);
return 0;
}
D - AABCC
为什么三重循环能过/fn
很明显，数的数量就是 \(a,b,c\) 的数量，因为唯一分解定理。
由于 \(a<b<c\)，所以 \(a^2\times b\times c^2>a^5\)，所以 \(a\) 只有 \(\sqrt[5]{n}\)，简单计算一下发现只有 \(251\)。同理可得 \(b\) 只有 \(\sqrt[3]{n}\)，是 \(10^4\)，所以同时枚举 \(a\) 和 \(b\) 也不会炸。
由于 \(c\) 是 \(\sqrt{n}\) 级别的，所以先筛出 \([2,10^6]\) 范围的质数。由于现在已经知道了 \(a,b\)，所以 \(c^2\) 的最大值为 \(\lfloor\frac{n}{a^2\times b}\rfloor\)，而最小值为 \(b\) 的下一个质数。筛的同时维护一下质数的平方，二分一下即可。
然后可以加几个剪枝（\(>n\) 退出），这样就跑得飞快了。
时间复杂度 \(O(\sqrt{n}+\frac{\sqrt[5]{n}}{\ln \sqrt[5]{n}}\frac{\sqrt[3]{n}}{\ln \sqrt[3]{n}}\log\frac{n}{\ln n})\)。完全可以通过。
代码：
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define gt getchar
#define pt putchar
#define y1 y233
#define re register
//typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 lll;
//typedef __uint128_t ulll;
const int N=1e6+5;
const int SIZE=1<<14;
using namespace std;
inline bool __(char ch){return ch>=48&&ch<=57;}
inline char gc(){
static char buf[SIZE],*begin=buf,*end=buf;
return begin==end&&(end=(begin=buf)+fread(buf,1,SIZE,stdin),begin==end)?EOF:*begin++;
}
inline ll read(){
ll x=0;bool sgn=0;char ch=gc();
while(!__(ch)&&ch!=EOF){sgn|=(ch=='-');ch=gc();}
while(__(ch)){x=(x<<1)+(x<<3)+(ch-48);ch=gc();}
return sgn?-x:x;
}
template<class T>
inline void print(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);
}
template<class T>
inline void printsp(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(32);
}
template<class T>
inline void println(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(10);
}
inline void put_str(string s){
int siz=s.size();
for(int i=0;i<siz;++i) pt(s[i]);
printf("\n");
}
ll n,ans,pf[N];
int cnt,prime[N];
bitset<N>not_prime;
inline void do_prime(int n){
not_prime[0]=not_prime[1]=1,cnt=0;
for(re int i=2;i<=n;++i){
if(!not_prime[i]){
prime[++cnt]=i;
pf[cnt]=1ll*i*i;
}
for(re int j=1;j<=cnt&&i*prime[j]<=n;++j){
not_prime[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
signed main(){
n=read();
do_prime(ceil(sqrt(n)));
for(re int i=1;i<=cnt&&prime[i]<=min(251ll,n);++i){
ll a=prime[i];
if(a*a*a*a*a>n)break;
for(re int j=i+1;j<=cnt&&prime[j]<=min((ll)1e4,n);++j){
ll b=prime[j];
if(b*b*b>n)break;
ll tmp=n/(a*a*b);
if(tmp<0)break;
int l=j+1,r=upper_bound(pf+1,pf+cnt+1,tmp)-pf-1;
if(l>r)continue;
ans+=(r-l+1);
}
}
println(ans);
return 0;
}
E - Dice Product 3
我们记 \(dp_i\) 表示当前为 \(i\) 时扔到 \(n\) 的概率。很明显，有：
\[dp_i=\begin{cases} 0,i>n \\ 1,i=n \\ \dfrac{dp_i+dp_{2i}+dp_{3i}+dp_{4i}+dp_{5i}+dp_{6i}}{6},i<n \end{cases} \]但是我们会发现 \(i<n\) 时，式子的两边都有 \(dp_i\)，移项整理一下：
\[dp_i-\dfrac{dp_i}{6}=\dfrac{dp_{2i}+dp_{3i}+dp_{4i}+dp_{5i}+dp_{6i}}{6} \]\[\dfrac{5dp_i}{6}=\dfrac{dp_{2i}+dp_{3i}+dp_{4i}+dp_{5i}+dp_{6i}}{6} \]\[5dp_i=dp_{2i}+dp_{3i}+dp_{4i}+dp_{5i}+dp_{6i} \]\[dp_i=\dfrac{dp_{2i}+dp_{3i}+dp_{4i}+dp_{5i}+dp_{6i}}{5} \]这样转移的时候用费马小定理算一下 \(5\) 的逆元就行。
由于 \(n\le10^{18}\)，所以明显不能直接递推。由于每次乘 \(2,3,4,5,6\) 是呈指数级递增的，再由于 \(2\) 到 \(6\) 每个数都可以拆解为 \(2,3,5\) 这三个质数的乘积，所以会用到的状态数实际上只有 \(\log^3\) 级别。
于是记搜即可。时间复杂度 \(O(\log^4n)\)，因为 map。
代码：
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define gt getchar
#define pt putchar
#define y1 y233
//typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 lll;
//typedef __uint128_t ulll;
const int mod=998244353;
using namespace std;
inline bool __(char ch){return ch>=48&&ch<=57;}
inline ll read(){
ll x=0;bool sgn=0;char ch=gt();
while(!__(ch)&&ch!=EOF){sgn|=(ch=='-');ch=gt();}
while(__(ch)){x=(x<<1)+(x<<3)+(ch-48);ch=gt();}
return sgn?-x:x;
}
template<class T>
inline void print(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);
}
template<class T>
inline void printsp(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(32);
}
template<class T>
inline void println(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(10);
}
inline void put_str(string s){
int siz=s.size();
for(int i=0;i<siz;++i) pt(s[i]);
printf("\n");
}
ll n,i5;
inline ll ksm(ll a,ll b){
ll res=1;a%=mod;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod,b>>=1;
}
return res;
}
map<ll,ll>dp;
ll dfs(ll now){
if(now>=n) return now==n;
if(dp.count(now)) return dp[now];
ll ans=0;
for(int i=2;i<=6;++i) ans=(ans+dfs(now*i))%mod;
return dp[now]=ans*i5%mod;
}
signed main(){
n=read(),i5=ksm(5,mod-2);
println(dfs(1));
return 0;
}
F - More Holidays
首先计算出 \(S\) 当中 \(x\) 的个数 \(cntx\)，然后计算出一共可以把多少个 \(S\) 整个变成 \(o\)。很明显，答案就是 \(\lfloor\frac{k}{cntx}\rfloor\)。如果这个东西已经 \(\ge m\)，那么直接输出 \(n\times m\) 走人。
否则，我们考虑用剩下的 \(k\) 去再整一些空隙。由于覆盖的 \(\lfloor\frac{k}{cntx}\rfloor\) 个没必要是从头覆盖，所以实际上可以从任意一个 \([1,n]\) 之间的位置 \(l\) 前面开始和结束。我们考虑枚举 \(r\)，并且计算最右能延伸到的位置 \(r\)。首先剩下的 \(k\) 是一定不会超过 \(cntx\) 的，所以最多只能跨越两段的距离。如果 \(\lfloor\frac{k}{cntx}\rfloor=m-1\)，那么只能延伸一段；否则，要考虑延伸两端。
我们用前缀和 \(sum_i\) 表示 \(S\) 的前 \(i\) 个字符中有多少个 \(x\)，这里由于可能跨越两段所以要把 \(S\) 倍长。很明显，只有最终的区间 \([l,r]\) 中的 \(x\) 个数不超过剩下的 \(k\) 才可以完全消除。根据区间和公式，有 \(sum_r-sum_{l-1}\le k\)，移项得 \(sum_r\le sum_{l-1}+k\)。直接在 \(sum\) 里查找最后一个 \(\le sum_{l-1}+k\) 的位置，使用 upper_bound-1 即可。
最后对于所有的 \(l\)，取 \(r-l+1\) 的最大值，再加上整段的答案 \(\lfloor\frac{k}{cntx}\rfloor\times n\) 即可。
不要忘记开 long long！
时间复杂度 \(O(n\log n)\)。
代码：
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define gt getchar
#define pt putchar
#define y1 y233
//typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 lll;
//typedef __uint128_t ulll;
const int N=6e5+5;
using namespace std;
inline bool __(char ch){return ch>=48&&ch<=57;}
inline ll read(){
ll x=0;bool sgn=0;char ch=gt();
while(!__(ch)&&ch!=EOF){sgn|=(ch=='-');ch=gt();}
while(__(ch)){x=(x<<1)+(x<<3)+(ch-48);ch=gt();}
return sgn?-x:x;
}
template<class T>
inline void print(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);
}
template<class T>
inline void printsp(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(32);
}
template<class T>
inline void println(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(10);
}
inline void put_str(string s){
int siz=s.size();
for(int i=0;i<siz;++i) pt(s[i]);
printf("\n");
}
ll ans,n,m,k,cntx,sum[N];
char s[N];
signed main(){
n=read(),m=read(),k=read();
scanf("%s",s+1);
for(int i=1;i<=n;++i){
cntx+=(s[i]=='x');
sum[i]=sum[i-1]+(s[i]=='x');
}
for(int i=n+1;i<=2*n;++i) sum[i]=sum[i-1]+(s[i-n]=='x');
ll cnt=k/cntx;
if(cnt>=m){
println(n*m);
return 0;
}
ans=1ll*n*cnt,k-=1ll*cnt*cntx;
ll len=0;
for(ll l=1;l<=n;++l){
ll r=0;
if(cnt==m-1) r=upper_bound(sum+l,sum+n+1,k+sum[l-1])-sum-1;
else r=upper_bound(sum+l,sum+2*n+1,k+sum[l-1])-sum-1;
len=max(len,r-l+1);
}
println(ans+len);
return 0;
}
G - P-smooth number
meet in the middle.
转换一下题目，实际上就相当于用 \([2,p]\) 内的质数凑出不超过 \(n\) 的数，问能凑出几个。
很明显这个数的数量也是质因子组合的数量，同样是因为唯一分解定理。
首先把 \(100\) 以内的质数筛出来，发现只有 \(25\) 个，考虑折半搜索。
先搜第一半的，枚举当前质数的指数，只要不超过 \(n\) 就乘起来，最后存到一个数组里。最终数量不会很多，开 \(10^7\) 足够了（也可以直接用爆搜算出数量）。
然后第二部分的搜法一样，最后只需要求第一半有多少个数不超过 \(\frac{n}{\text{当前数}}\)，对第一半数组排序二分即可。
由于前一半的数比较小，所以如果是 \(\lfloor\frac{n}{2}\rfloor\) 个数的话会卡死。输出一下变量发现大概会卡在 \(12\) 左右，改成 \(\lfloor\frac{n}{3}\rfloor\) 即可。
时间复杂度 \(O(\text{能过})\)。
代码：
#include<bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define gt getchar
#define pt putchar
#define y1 y233
//typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 lll;
//typedef __uint128_t ulll;
const int N=1e7+5;
using namespace std;
inline bool __(char ch){return ch>=48&&ch<=57;}
inline ll read(){
ll x=0;bool sgn=0;char ch=gt();
while(!__(ch)&&ch!=EOF){sgn|=(ch=='-');ch=gt();}
while(__(ch)){x=(x<<1)+(x<<3)+(ch-48);ch=gt();}
return sgn?-x:x;
}
template<class T>
inline void print(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);
}
template<class T>
inline void printsp(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(32);
}
template<class T>
inline void println(T x){
static char st[70];short top=0;
if(x<0)pt('-');
do{st[++top]=x>=0?(x%10+48):(-(x%10)+48),x/=10;}while(x);
while(top)pt(st[top--]);pt(10);
}
inline void put_str(string s){
int siz=s.size();
for(int i=0;i<siz;++i) pt(s[i]);
printf("\n");
}
ll n,a[N],ans;
int p,cnt,prime[105],tot;
bool not_prime[105];
inline void do_prime(int n){
not_prime[0]=not_prime[1]=1,cnt=0;
for(int i=2;i<=n;++i){
if(!not_prime[i]) prime[++cnt]=i;
for(int j=1;j<=cnt&&i*prime[j]<=n;++j){
not_prime[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
void dfs1(int now,int limit,ll val){
if(now>limit){
a[++tot]=val;
return;
}
dfs1(now+1,limit,val);
while(1){
val*=prime[now];
if(val>n) break;
dfs1(now+1,limit,val);
}
}
void dfs2(int now,int limit,ll val){
if(now>limit){
ll tmp=n/val;
ll sum=upper_bound(a+1,a+tot+1,tmp)-a-1;
ans+=sum;
return;
}
dfs2(now+1,limit,val);
while(1){
val*=prime[now];
if(val>n) break;
dfs2(now+1,limit,val);
}
}
signed main(){
n=read(),p=read();
do_prime(p);
dfs1(1,cnt/3,1);
sort(a+1,a+tot+1);
dfs2(cnt/3+1,cnt,1);
println(ans);
return 0;
}
Ex - Fibonacci: Revisited
是多项式，这下 AK 不了了……
标签：10,48,AK,ABC300,st,How,while,x%,top From： https://www.cnblogs.com/syzqwq/p/18040559