A.Pawn on a Grid
题意:给一个矩阵,求出 “#” 的个数
题解:枚举即可。
代码:
#include<bits/stdc++.h>
using namespace std;
char a[15][15];int cou=0;
int read(){
int x=0,f=0,ch=getchar();
for(;ch<'0' || ch>'9';ch=getchar()){
f|=(ch=='-');
}
for(;ch>='0' && ch<='9';ch=getchar()){
x=(x<<3)+(x<<1)+(ch^48);
}
return f?~(x-1):x;
}
void write(int x){
if(x<0){
putchar('-');
x=~(x-1);
}
if(x>9){
write(x/10);
}
putchar(x%10+'0');
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
if(a[i][j]=='#'){
cou++;
}
}
}
cout<<cou;
return 0;
}
B.Inverse Prefix Sum
题意:求差分数组。
题解:模拟即可。
代码:
#include<bits/stdc++.h>
using namespace std;
int n,a[1005];
int read(){
int x=0,f=0,ch=getchar();
for(;ch<'0' || ch>'9';ch=getchar()){
f|=(ch=='-');
}
for(;ch>='0' && ch<='9';ch=getchar()){
x=(x<<3)+(x<<1)+(ch^48);
}
return f?~(x-1):x;
}
void write(int x){
if(x<0){
putchar('-');
x=~(x-1);
}
if(x>9){
write(x/10);
}
putchar(x%10+'0');
}
int main(){
n=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
for(int i=1;i<=n;i++){
if(i==1){
write(a[i]);
putchar(' ');
}else{
write(a[i]-a[i-1]);
putchar(' ');
}
}
return 0;
}
C. Extra Character
题意:找额外的字符。
题解:模拟即可,遇到不一样的输出,然后退出。
代码:
#include<bits/stdc++.h>
using namespace std;
char a[500005],b[500005];
int read(){
int x=0,f=0,ch=getchar();
for(;ch<'0' || ch>'9';ch=getchar()){
f|=(ch=='-');
}
for(;ch>='0' && ch<='9';ch=getchar()){
x=(x<<3)+(x<<1)+(ch^48);
}
return f?~(x-1):x;
}
void write(int x){
if(x<0){
putchar('-');
x=~(x-1);
}
if(x>9){
write(x/10);
}
putchar(x%10+'0');
}
int main(){
cin>>(a+1)>>(b+1);
for(int i=1;i<=strlen(b+1);i++){
if(a[i]!=b[i]){
write(i);
return 0;
}
}
return 0;
}
D. Factorial and Multiple
题意:求最小的 $n$ 使得 $n!$ 为 $k$ 的倍数。
题解:线性筛,分解质因数,然后利用约数和次数,求出最大的 $n$。
代码:
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
long long K,is_p[2000005],prime[2000005],cnt;
vector<pair<long long,long long> > vec;
long long ans;
long long read(){
long long x=0,f=0,ch=getchar();
for(;ch<'0' || ch>'9';ch=getchar()){
f|=(ch=='-');
}
for(;ch>='0' && ch<='9';ch=getchar()){
x=(x<<3)+(x<<1)+(ch^48);
}
return f?~(x-1):x;
}
void write(long long x){
if(x<0){
putchar('-');
x=~(x-1);
}
if(x>9){
write(x/10);
}
putchar(x%10+'0');
}
void shai(){
for(int i=2;i<N;i++){
if(!is_p[i]){
prime[++cnt]=i;
}
for(int j=1;j<=cnt&&prime[j]<N/i;j++){
is_p[prime[j]*i]=prime[j];
if(i%prime[j]==0){
break;
}
}
}
}
int main(){
K=read();
shai();
for(long long i=1;prime[i]<=K/prime[i];i++){
long long p=(long long)prime[i];
if(K%p==0){
long long ccc=0;
while(K%p==0){
ccc++;
K/=p;
}
vec.push_back({p,ccc});
}
}
if(K>1){
vec.push_back({K,1});
}
for(long long j=0;j<vec.size();j++){
long long p=vec[j].first,temp=vec[j].second;
for(long long i=p;1;i+=p){
long long cnt=0,res=i,ii=i;
while(ii%p==0){
cnt++;
ii/=p;
}
temp-=cnt;
if(temp<=0){
ans=max(ans,res);
break;
}
}
}
printf("%lld",ans);
return 0;
}
/*
123456789012
*/
E.Critical Hit
题意:给定一个数 有 $p%$ 的概率减 $1$,有 $1-p%$ 的概率减少 $2$,求小于 $1$ 时的期望次数。
题解:期望 $dp$,先要求出 $100$ 的逆元。
代码:
#include<bits/stdc++.h>
#define mod 998244353
using namespace std;
int n;
long long p;
long long f[200005];
long long ksm(long long a,long long b){
long long res=1;
while(b){
if(b%2==1){
res=res*a%mod;
}
a=a*a%mod;
b/=2;
}
return res;
}
int main(){
scanf("%d%lld",&n,&p);
p=p*ksm(100,mod-2)%mod;
f[1]=1;
for(int i=2;i<=n;i++){
f[i]=(p*f[i-2]+(mod+1-p)%mod*f[i-1]+1)%mod;
}
printf("%lld",f[n]);
return 0;
}