B - Measure
难度: ⭐
题目大意
给定一个数N, 我们要求输出长度为n+1的一个序列Si(i从0到n), 对于Si, 如果存在j(j从1~9)是N的一个除数, 并且i是N/j的一个倍数, 那么Si就是满足条件的最小的j, 如果没存在就输出'-';
解题思路
数据不大, 暴力即可;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 3e5 + 10, mod = 998244353;
typedef pair<string, int> PSI;
int n, m, res;
signed main() {
cin >> n;
for (int i = 0; i <= n; i++) {
bool f = false;
for (int j = 1; j <= 9; j++) {
if (!(n % j) && !(i%(n / j))) {
f = true;
cout << j;
break;
}
}
if (!f) cout << '-';
}
return 0;
}
C - False Hope
难度: ⭐⭐
题目大意
给定一个3*3的矩阵, 该矩阵一开始是盖住的, 小莫每次会从未翻开的格子种随机翻开一个, 如果某一行/列/对角线上, 三个值中小莫翻开的前两个值是相同的, 那么这次观看顺序就是非法的; 请问有多少种合法的观看顺序;
解题思路
这个题真的是...不好评价, 反正是不想做第二次了;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 3e5 + 10, mod = 998244353;
typedef pair<string, int> PSI;
int n, m, res;
int a[10],d[10];
bool flag[10];
signed main(){
for(int i = 1;i <= 9;i++){
d[i] = i;
cin >> a[i];
}
long long cnt1 = 0,cnt2 = 0;
do{
cnt1++;
memset(flag,0,sizeof(flag));
for(int i = 1;i <= 9;i++){
flag[d[i]] = 1;
if(d[i] == 1){
if(flag[2] && flag[3] && a[2] == a[3]){
cnt2++;
break;
}
if(flag[4] && flag[7] && a[4] == a[7]){
cnt2++;
break;
}
if(flag[5] && flag[9] && a[5] == a[9]){
cnt2++;
break;
}
}
if(d[i] == 2){
if(flag[1] && flag[3] && a[1] == a[3]){
cnt2++;
break;
}
if(flag[5] && flag[8] && a[5] == a[8]){
cnt2++;
break;
}
}
if(d[i] == 3){
if(flag[1] && flag[2] && a[2] == a[1]){
cnt2++;
break;
}
if(flag[6] && flag[9] && a[6] == a[9]){
cnt2++;
break;
}
if(flag[5] && flag[7] && a[5] == a[7]){
cnt2++;
break;
}
}
if(d[i] == 4){
if(flag[1] && flag[7] && a[1] == a[7]){
cnt2++;
break;
}
if(flag[5] && flag[6] && a[5] == a[6]){
cnt2++;
break;
}
}
if(d[i] == 5){
if(flag[4] && flag[6] && a[4] == a[6]){
cnt2++;
break;
}
if(flag[2] && flag[8] && a[2] == a[8]){
cnt2++;
break;
}
if(flag[1] && flag[9] && a[1] == a[9]){
cnt2++;
break;
}
if(flag[3] && flag[7] && a[3] == a[7]){
cnt2++;
break;
}
}
if(d[i] == 6){
if(flag[4] && flag[5] && a[4] == a[5]){
cnt2++;
break;
}
if(flag[3] && flag[9] && a[3] == a[9]){
cnt2++;
break;
}
}
if(d[i] == 7){
if(flag[8] && flag[9] && a[8] == a[9]){
cnt2++;
break;
}
if(flag[4] && flag[1] && a[4] == a[1]){
cnt2++;
break;
}
if(flag[3] && flag[5] && a[5] == a[3]){
cnt2++;
break;
}
}
if(d[i] == 8){
if(flag[2] && flag[5] && a[2] == a[5]){
cnt2++;
break;
}
if(flag[9] && flag[7] && a[9] == a[7]){
cnt2++;
break;
}
}
if(d[i] == 9){
if(flag[7] && flag[8] && a[7] == a[8]){
cnt2++;
break;
}
if(flag[6] && flag[3] && a[3] == a[6]){
cnt2++;
break;
}
if(flag[1] && flag[5] && a[5] == a[1]){
cnt2++;
break;
}
}
}
}while(next_permutation(d+1,d+10));
printf("%.10f",1.0-1.0*cnt2/cnt1);
return 0;
}
D - Minimum Width
难度: ⭐⭐
题目大意
现在有一个由n个单词组成的句子, 给出这n个单词各自的长度; 我们要在一个矩形窗口中展示这个句子, 已知这个窗口最多可以显示m行, 请问窗口的宽度最短设为多少可以展示出完整的句子; 注意单词之间有空格, 换行的话就不用空格了;
解题思路
算是一个比较明显的二分, 二分宽带, 然后遍历每个单词看看能否装下就可以了;
神秘代码
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, res;
int L[N];
bool check(int u){
int len=L[1], num=1;
for(int i=2;i<=n;i++){
if(len+L[i]+1>u){
num++;
len=L[i];
}
else len+=L[i]+1;
}
if(num<=m) return true;
else return false;
}
signed main(){
cin>>n>>m;
int l=0,r=1e16;
for(int i=1;i<=n;i++){
cin>>L[i];
l=max(l,L[i]);
}
while(l<r){
int mid=l+r>>1;
if(check(mid)){
r=mid;
}
else l=mid+1;
}
cout<<l<<endl;
return 0;
}
E - Bus Stops
难度: ⭐⭐⭐
题目大意
小莫家和安姐家之间有n个公交站, 已知小莫从家到第一个公交站的时间是x, 从第n个公交站到安姐家的时间是y; 1n-1个公交站都有两个属性Pi和Ti~, 该公交站的公交车会等到Pi的倍数的时间才会发车, (Pi范围是1~8) 并且到下一个公交站所需的时间是Ti; 给定Q个询问, 每个询问给出小莫从家出发的时间是多少, 输出什么时候到达安姐家;
解题思路
从数据范围可以看出肯定不能模拟, 一定会超时; 所以需要考虑预处理; 根据每个站牌的公交车出发时间规律, 我们计算出1到8的最小公倍数是840, 也就是说每840分钟是一个周期, 从0分钟出发和第840分钟出发, 途中所耗的时间是一样的; 这样我们需要算840中情况即可, 每次询问k的答案就是k+res[k%840];
神秘代码
##include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 2e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m;
int p[N], t[N], res[N];
signed main(){
IOS;
int x, y;
cin>>n>>x>>y;
for(int i=1;i<n;i++){
cin>>p[i]>>t[i];
}
for(int i=0;i<=839;i++){
int k=i+x;
for(int j=1;j<n;j++){
int a=k%p[j];
if(a) a=p[j]-a;
k = k+a+t[j];
}
res[i]=k+y-i;
}
cin>>m;
while(m--){
int k;
cin>>k;
cout<<k+res[k%840]<<endl;
}
return 0;
}
F - Fighter Takahashi
难度: ⭐⭐⭐⭐⭐
- Beginner AtCoder Contest 319 abcbeginner atcoder contest 319 beginner atcoder contest abc contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334