用时
如果算上颓废时间的话
| T1 | T2 | T3 | T4 | |
|---|---|---|---|---|
| 用时 | (0.5h) | (1.5h) | (1.5h) | (0) |
| 得分 | (100) | (100) | (40) | (0) |
T1
求(A<|O|)
注意会爆$long long (需要开)ull$
**注意输入的(O)有负数（坑 **
代码就不放了
T2
第一眼看感觉像(dp)，但是推不出来
思路就是每一个条形单独考虑
如果这个条有(n)个座位(k*(k-1)^{n-1})
利用乘法原理计算最后的答案即可
这题不应该用那么长时间，哎呀，还是菜
/*
@ author:pyyyyyy
-----思路------
-----debug-------
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
const int N=1e3+2020;
int dx[5]= {0,-1,1,0,0};
int dy[5]= {0,0,0,-1,1};
int a[N][N],n,m,k,tot;
int ans=1,vis[N][N],tmp,flag=0;
void dfs(int x,int y,int lx,int ly) {
if(a[x-1][y]+a[x+1][y]+a[x][y-1]+a[x][y+1]>2) {
flag=1;
return ;
}
for(int i=1; i<=4; ++i) {
int nowx=x+dx[i];
int nowy=y+dy[i];
if(a[nowx][nowy]==1&&(nowx!=lx||nowy!=ly)) {
if(!vis[nowx][nowy]) {
vis[nowx][nowy]=1;
tmp=(tmp*(k-1))%mod;
dfs(nowx,nowy,x,y);
} else flag=1;
}
}
}
signed main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>n>>m>>k;
for(int i=1; i<=n; ++i) {
for(int j=1; j<=m; ++j) {
char opt;
cin>>opt;
if(opt=='O') a[i][j]=1;
else a[i][j]=0;
}
}
for(int i=1; i<=n; ++i)
for(int j=1; j<=m; ++j) {
if(!vis[i][j]&&a[i][j]==1) {
vis[i][j]=1;
tmp=k;
dfs(i,j,i,j);
if(flag) {
cout<<0;
return 0;
}
ans=(ans*tmp)%mod;
}
}
cout<<ans%mod;
return 0;
}
T3
约分后分母中只含有(2,5)这两个质因子的数就是有限小数
(40pts)
暴力(O(n^2))直接统计即可
(80pts)
(100pts)
不会
/*
@ author:pyyyyyy
-----思路------
-----debug-------
*/
#include<bits/stdc++.h>
using namespace std;
int n,cnt;
int gcd(int a,int b) {
if(!b) return a;
else return gcd(b,a%b);
}
int judge(int x,int y) {
int d=gcd(x,y);
x/=d;
y/=d;
for(int i=2; i*i<=y; ++i) {
if(y%i==0) {
if(i!=2&&i!=5) return 0;
while(y%i==0) y/=i;
}
}
if(y>1&&y!=2&&y!=5) return 0;
return 1;
}
int cnts[100];
int main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>n;
for(int x=1; x<=n; ++x) {
// cout<<x<<':';
int js=0;
for(int y=1; y<=n; ++y)
if(judge(x,y)==1) {
// cout<<y<<' ';
js++;
}
// cout<<js;
cnts[x]=js;
// cout<<',';
}
for(int i=1;i<=30;++i) cnts[i]-=cnts[i-1];
for(int i=1;i<=30;++i) cout<<cnts[i]<<' ';
// if(judge(x,y)==1) cnt++;
// cout<<cnt;
return 0;
}
/*
1:1 2 4 5 8 10 16 20 25
2:1 2 4 5 8 10 16 20 25
3:1 2 3 4 5 6 8 10 12 15 16 20 24 25 30
4:1 2 4 5 8 10 16 20 25
5:1 2 4 5 8 10 16 20 25
6:1 2 3 4 5 6 8 10 12 15 16 20 24 25 30
7:1 2 4 5 7 8 10 14 16 20 25 28
8:1 2 4 5 8 10 16 20 25
9:1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 30
10:1 2 4 5 8 10 16 20 25
11:1 2 4 5 8 10 11 16 20 22 25
12:1 2 3 4 5 6 8 10 12 15 16 20 24 25 30
13:1 2 4 5 8 10 13 16 20 25 26
14:1 2 4 5 7 8 10 14 16 20 25 28
15:1 2 3 4 5 6 8 10 12 15 16 20 24 25 30
16:1 2 4 5 8 10 16 20 25
17:1 2 4 5 8 10 16 17 20 25
18:1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 30
19:1 2 4 5 8 10 16 19 20 25
20:1 2 4 5 8 10 16 20 25
21:1 2 3 4 5 6 7 8 10 12 14 15 16 20 21 24 25 28 30
22:1 2 4 5 8 10 11 16 20 22 25
23:1 2 4 5 8 10 16 20 23 25
24:1 2 3 4 5 6 8 10 12 15 16 20 24 25 30
25:1 2 4 5 8 10 16 20 25
26:1 2 4 5 8 10 13 16 20 25 26
27:1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30
28:1 2 4 5 7 8 10 14 16 20 25 28
29:1 2 4 5 8 10 16 20 25 29
30:1 2 3 4 5 6 8 10 12 15 16 20 24 25 30
*/
T4
不会