A - N-choice question
题目大意
从n个数里面找出a+b的结果
解题思路
签到题不多嗦了
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 310;
int n;
signed main() {
int a, b;
cin >> n >> a >> b;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (x == a + b) cout << i;
}
return 0;
}
B - Same Map in the RPG World
题目大意
给定两个矩阵a和b, 现在可以对b进行两种操作: 一是把矩阵的行向上移一行, 即由1 2 3 4变成2 3 4 1; 二是把矩阵的列向左移一列; 问是否能通过有限次操作让两个矩阵相同;
解题思路
因为行和列的数量都小于30; 所有直接暴力即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 35;
char a[N][N];
char b[N][N];
int n,m;
bool check( int y, int z) {
bool f = true;
for (int i=1,j = y; i<=n; i++,j++) {
if (j > n) j = 1;
for (int k = z, h = 1; h<=m; k++, h++) {
if (k > m) k = 1;
if (a[i][h] != b[j][k]) {
f = false;
break;
}
}
if (!f) break;
}
if (f) return true;
else return false;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> b[i][j];
}
}
char s = a[1][1];
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= m; k++) {
if (b[j][k] == s) {
if (check( j, k)) {
cout << "Yes";
return 0;
}
}
}
}
cout << "No";
return 0;
}
C - Cross
题目大意
给定一个只有'#'和'.'组成的矩阵, 问由'#'组成的X形状的各种大小的都有多少个
解题思路
数量不大, 直接暴力
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
char g[N][N];
int dx[] = { 1,1,-1,-1 }, dy[] = { 1,-1,1,-1 };
int n,m;
map<int, int> mp;
void check(int x, int y) {
bool f = true;
int idx = 0;
while (1) {
for (int i = 0; i < 4; i++) {
int a = x + dx[i]*(idx+1), b = y + dy[i]*(idx+1);
if (a<1 || a>n || b<1 || b>m||g[a][b] != '#') {
f = false;
break;
}
}
if (!f) break;
idx++;
}
mp[idx]++;
}
signed main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> g[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (g[i][j] == '#') {
check(i, j);
}
}
}
int num = min(n, m);
for (int i = 1; i <= num; i++) {
cout << mp[i] << ' ';
}
return 0;
}
D - AABCC
题目大意
现在有三个质数a,b,c;(a<b<c) 现在定义一个数为a * a * b * c * c; 给定一个数n, 问不超过n的数里存在多少个这样的数
解题思路
先用线性筛出质数, 然后还是暴力...不过要注意每选一个数都要判定一次, 要不然会tle
注意这里有个坑, 因为n最大为1e12, 所以我们可以只找1e6以内的质数; 但是如果a,b,c都是1e6的数量级, 结果还是会爆long long, c会变成负数也被判定为小于n, 使答案错误; 对于我们在选a和b时, 筛选条件不能只是a* a和a* a* b, 而应该是a* a* a* a* a和a* a* b* b* b, 这样可以有效防止上述情况;
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6+10;
int n,num=0;
bool st[N];
int p[N];
void ini() {
for (int i = 2; i <= N; i++) {
if (!st[i]) p[num++] = i;
for (int j = 0; p[j] * i <= N; j++) {
st[i * p[j]] = true;
if (i % p[j]==0) break;
}
}
}
signed main() {
cin >> n;
int idx = 0;
ini();
for (int i = 0; i < num - 2; i++) {
int maxn = 0;
int a = p[i] * p[i] * p[i] * p[i] * p[i];
if (a > n) break;
for (int j = i + 1; j < num - 1; j++) {
int b = p[i] * p[i] * p[j] * p[j] * p[j];
if (b > n) break;
for (int k = j + 1; k < num; k++) {
int c = p[k] * p[k] * p[j] * p[i] * p[i];
if (c <= n) {
idx++;
}
else break;
}
}
}
cout << idx;
return 0;
}
E - Dice Product 3
题目大意
给定一个数m初始值为1, 现有一个骰子, 可以等可能地得到1~6之间的一个数; 然后用m乘这个数来更新m; 现在给定一个数n, 只要m小于n就可以一直进行这个操作, 问m恰好可以等于n的概率为多少, 结果对998244353取模;
解题思路
这个是真不会; 一开始样例都看不明白...题解用的是记忆化搜索(这块我是真不熟...)
我先解释一下样例, 样例中n=6; 我们可以先想到如果想得到6, 那么一定是由6的因数得来的, 比如1 2 3 6; 我们设f6为当前m为6的概率, 则 f6 = ( f1+ f2+ f3+ f6) / 6;把f6移项得到 f6 = ( f1+ f2+ f3) / 5; 同理 f2 = f1/5, f3 = f1/5; 这样就得到 f6 = 7/25 * f1; 因为m初识为1, 所以f1就是1; 故f6 = 7/25; 因为239578645 * 25 ≡ 7 (mod 998244353) 故答案为239578645; 因为5对998244353的逆元为598946612, 所以我们在过程中把除以5变成乘5的逆元即可直接得到答案;
关于什么时候用记忆化搜索, 我感觉是当我们的递推过程中频繁出现之前求过的数, 那我们可以把之前求过的数都存起来, 用的时候直接取出来即可; (因为记忆化搜索地过程朴素地简直不像是一个算法, 所以一直都没怎么思考过它...)
神秘代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> PII;
const int mod = 998244353;
map<int, int> mp;
int n;
int idx= 598946612;
int check(int x) {
int res=0;
if (mp[x]) return mp[x];
for (int i = 2; i <= 6; i++) {
if (x % i == 0) res= (res+check(x/i))%mod;
}
mp[x] = res * idx % mod;
return mp[x];
}
signed main() {
mp[1] = 1;
cin >> n;
cout<<check(n);
return 0;
}
F - More Holidays
题目大意
待定.....
解题思路
待定....
神秘代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1e6+10;
int w[N],d[N];
int n,m,idx;
bool st[N];
vector<int> v[N];
int dijkstra(){
memset(d,0x3f,sizeof d);
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,1});
d[1]=0;
while(heap.size()){
auto t=heap.top();
heap.pop();
int x=t.second;
if(st[x]) continue;
st[x]=true;
for(int p:v[x]){
if(d[p]>d[x]+w[p]){
d[p]=d[x]+w[p];
heap.push({d[p],p});
}
}
}
if(d[m]==0x3f3f3f3f) return -1;
else return d[m]-1;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int k;
cin>>k;
w[i+m] =1;
for(int j=1;j<=k;j++){
int x;
cin>>x;
v[x].push_back(i+m);
v[i+m].push_back(x);
}
}
cout<<dijkstra();
return 0;
}