AtCoder Beginner Contest 367 A~D

本期封面原图 画师えびら

A - Shout Everyday

题意

b点睡觉c点起床，问你a点是不是醒着的

思路

直接判断即可，注意处理跨天的情况

代码

#include <bits/stdc++.h>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;int main()
{int a,b,c;cin >> a >> b >> c;if(b>c){if(a>=b or a<=c)cout << "No";elsecout << "Yes";return 0;}if(b<=a && a<=c)cout << "No";elsecout << "Yes";return 0;
}

B - Cut .0

题意

给你一个数，去掉他的无效0，也就是小数点右边末尾的和小数点左边最前面的

思路

直接模拟即可

代码

#include <bits/stdc++.h>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;int main()
{string s;cin >> s;//给一个数字，去掉无效0int n=s.length();string ans="";int flag=0;int i;for (i=0;i<n;i++){if(s[i]=='.')break;if(flag==0 and s[i]=='0')continue;else{flag=1;ans+=s[i];}}ans+='.';int j;for(j=n-1;j>i;j--){if(s[j]=='0')continue;elsebreak;}for(int k=i+1;k<=j;k++)ans+=s[k];if(ans[0]=='.')ans="0"+ans;if(ans[ans.length()-1]=='.')ans=ans.substr(0,ans.length()-1);cout << ans << endl;return 0;
}

C - Enumerate Sequences

题意

按升序排列打印所有满足以下条件的长度为 $N$ 的整数序列。

• 第 $i$ 个元素介于 $1$ 和 $R_i$ 之间（包括首尾两个元素）。
• 所有元素之和是 $K$ 的倍数。

思路

数据范围很小，所以直接dfs遍历即可

代码

#include <bits/stdc++.h>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n,k;
int r[10];
vector<int> ans(10);
void dfs(int dpt,int sum)
{if(dpt==n){if(sum%k==0){for (int i=0;i<n;i++) cout << ans[i] << " ";cout << endl;}return ;}for(int i=1;i<=r[dpt];i++){ans[dpt]=i;dfs(dpt+1,sum+i);}
}int main()
{cin >> n >> k;for (int i=0;i<n;i++) cin >> r[i];dfs(0,0);return 0;
}

D - Pedometer

题意

一个湖周围有 $N$ 个休息区。
休息区按顺时针顺序编号为 $1$ 、 $2$ 、…、 $N$ 。
从休息区 $i$ 顺时针走到休息区 $i+1$ 需要 $A_i$ 步（其中休息区 $N+1$ 指的是休息区 $1$ ）。
从休息区 $s$ 顺时针走到休息区 $t$ （ $s\ne t$ ）所需的最小步数是 $M$ 的倍数。
求 $(s,t)$ 的可能对数。

思路

我们可以直接前缀和，然后对前缀和每一个位置取模，模相等的那就说明从前面那个点走到右边那个点算是一对合法对。
然后考虑转了好几圈的情况，我们把这个湖拉直，然后继续往后加，也就是到1之后我还继续走下一轮，无限地往后计算前缀和

那么现在问题是什么时候结束呢？自然就是某一个点1的前缀和取模后刚好为0，这样就算是完成了一整次循环，最后计算即可

代码

#include <bits/stdc++.h>
#define mod 998244353
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N=4e5+5;
const int M=1e6+5;
ll n,m;
ll a[N];
ll pre[N];
ll cnt[M];
ll ans;int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= n; i++) {a[i+n] = a[i];}for (int i=1; i <= 2*n; i++) {pre[i] = pre[i-1]+a[i];}for (int i = 1; i <= 2*n; i++) {if (i <= n) {ans += cnt[pre[i]%m];cnt[pre[i]%m]++;} else {cnt[pre[i-n]%m]--;ans += cnt[pre[i]%m];}}cout << ans;return 0;
}