AtCoder Beginner Contest 275
A – Find Takahashi
题目描述：
给出n个数字，你需要找出最大的数字的下标
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];
void work(){
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> x;
if(x > k){
k = x;
m = i;
}
}
cout << m << endl;
}
int main(){
io;
work();
return 0;
}
B – ABC-DEF
题目描述：
输出
A*B*C-D*E*F
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
__int128 a, b, c, d, e ,f;
inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
void work(){
a = read();
b = read();
c = read();
d = read();
e = read();
f = read();
__int128 p = (((a * b)%mod9) * c) % mod9;
__int128 q = (((d * e)%mod9) * f) % mod9;
print(((p - q)%mod9 + mod9) % mod9);
}
int main(){
io;
work();
return 0;
}
C – Counting Squares
题目描述：
给定
9*9的方格，#代表点，.为空，问存在多少个正方形的顶点都是#，正方形的边长不一定平行于横与列
思路：
暴力枚举正方形的四个顶点，判四条边是否相同，并利用向量点乘计算是否垂直
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <double,double> pii;
#define MAX 300000 + 50
int n, m, k, x;
char tr[10][10];
vector<pii>v;
double getdis(int i, int j){
return sqrt((v[i].first - v[j].first)*(v[i].first - v[j].first) + (v[i].second - v[j].second) * (v[i].second - v[j].second));
}
bool judge(double x1, double x2, double y11, double y2){
if(x1 * x2 + y11 * y2 == 0)return true;
return false;
}
void work(){
n = 9;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
cin >> tr[i][j];
if(tr[i][j] == '#')v.push_back(m_p(i, j));
}
}
int ans = 0;
for(int i = 0; i < v.size(); ++i){
for(int j = i + 1; j < v.size(); ++j){
for(int k = j + 1; k < v.size(); ++k){
for(int p = k + 1; p < v.size(); ++p){
if(getdis(i, j) == getdis(i, k) && getdis(i, j) == getdis(j, p) && getdis(i, j) == getdis(k, p) && judge(v[i].first-v[j].first, v[i].first-v[k].first, v[i].second-v[j].second, v[i].second-v[k].second)){
++ans;
}
}
}
}
}
cout << ans << endl;
}
int main(){
io;
work();
return 0;
}
D – Yet Another Recursive Function
题目描述：
，求 f(n)
思路：
简单递归，记忆化一下就好
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
ll n;
map<ll,ll>mp;
ll cal(ll n){
if(mp.count(n))return mp[n];
mp[n] = cal(n/2) + cal(n/3);
return mp[n];
}
void work(){
mp[0] = 1;
cin >> n;
cout << cal(n) << endl;
}
int main(){
io;
work();
return 0;
}
E – Sugoroku 4
题目描述：
一个刻有
1-m的骰子，每次扔骰子都会等概率的扔出一个1到m的数字有一个
0到n的路，你现在在0号点，你会根据每次扔出的骰子大小走对应步数，如果到达n后,多余的步数会倒着往会走，比如你现在在5号点，扔到了4，n=6，则你先从5走到6，再从6走到3（下一次当然还是顺着走现在问你最多有
k次扔骰子的机会，能到达n点的概率是多少，输出对998244353取模后的结果
思路：
概率
dp
dp[i][j]表示扔了i次骰子后到达j点的概率枚举当前这次扔的是什么，然后进行递推
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 1000 + 50
int n, m, k, x;
ll dp[MAX][MAX];
ll q_pow(ll a, ll b, ll MOD){
ll ans = 1;
while(b > 0){
if(b & 1)ans = ans * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return ans;
}
inline ll getniyuan(ll a, ll p){
return q_pow(a, p - 2, p);
}
void work(){
cin >> n >> m >> k;
ll ni = getniyuan(m, mod9);
dp[0][0] = 1;
for(int i = 0; i < k; ++i){
for(int j = 0; j < n; ++j){
for(int p = 1; p <= m; ++p){
if(p <= n - j){
(dp[i+1][j + p] += (dp[i][j] * ni)%mod9)%=mod9;
}
else{
(dp[i+1][2*n-p-j] += (dp[i][j] * ni)%mod9)%=mod9;
}
}
}
}
ll ans = 0;
for(int i = 0; i <= k; ++i){
(ans = ans + dp[i][n]) %= mod9;
}
cout << ans << endl;
}
int main(){
io;
work();
return 0;
}
F – Erase Subarrays
题目描述：
给定长度为
n的数组a[i]，对于x = 1，2，…,m，我们需要计算最少需要删除多少段子区间后剩余数字的和能等于x
思路：
dp[i][j][0]表示前i个数字中，不选第i个数字时凑出j所需要删除的最小段数初始化所有值为
inf
dp[0][0][1]=0进行递推的时候就枚举每个点选或者不选
dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j][1])
dp[i][j][1] = min(dp[i-1][j-tr[i]][0]+1,dp[i-1][j-tr[i]][1]最后计算答案的时候是
min(dp[n][i][0]+1, dp[n][i][1])
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];
int dp[3003][3003][2];
void work(){
cin >> n >> m;
for(int i = 1; i <= n; ++i){
cin >> tr[i];
}
mem(dp, inf);
dp[0][0][1] = 0;
for(int i = 1; i <= n; ++i){
for(int j = 0; j <= m; ++j){
dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j][1]);
if(j >= tr[i])dp[i][j][1] = min(dp[i-1][j-tr[i]][0]+1, dp[i-1][j-tr[i]][1]);
}
}
for(int i = 1; i <= m; ++i){
int x = min(dp[n][i][0]+1, dp[n][i][1]);
if(x == inf)cout << -1 << endl;
else cout << x << endl;
}
}
int main(){
io;
work();
return 0;
}
