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;
}