Codeforces Round 1013 (Div. 3)（A-F）

题目链接：Dashboard - Codeforces Round 1013 (Div. 3) - Codeforces

A. Olympiad Date

思路

找到第一个位置能凑齐01032025的位置

代码

void solve(){int n;cin>>n;vi a(n+10);int id=0;map<int,int> mp;for(int i=1;i<=n;i++){cin>>a[i];mp[a[i]]++;if(!id&&mp[0]>=3&&mp[1]>=1&&mp[3]>=1&&mp[2]>=2&&mp[5]>=1){id=i;}}cout<<id<<"\n";
}

B. Team Training

思路

将数组a划分成不同的组别，最大化实力>=x的数量

贪心一下，如果a[i]>=x单独划分成一组，否则就多凑几个人到x

代码

void solve(){int n,x;cin>>n>>x;vi a(n+10);for(int i=1;i<=n;i++){cin>>a[i];}sort(a.begin()+1,a.begin()+1+n,greater<int>());int cnt=0;int t=1;for(int i=1;i<=n;i++){if(a[i]>=x){cnt++;}else{if(t*a[i]>=x){cnt++;t=1;}else{t++;}}}cout<<cnt<<"\n";
}

C. Combination Lock

思路

构造，说实话这题全靠猜，我赛时傻傻地看样例2构造n=7的情况，其实只需要倒序输出一下就行，或者如下这么构造也是可以的

代码

void solve(){int n;cin>>n;if(n%2==0){cout<<"-1\n";return;}vi ans(n+1);ans[1]=1;int t=n;for(int i=n-1;i>=1;i-=2){ans[i]=t--;}for(int i=n;i>=1;i-=2){ans[i]=t--;}for(int i=1;i<=n;i++){cout<<ans[i]<<" ";}cout<<"\n";
}

D. Place of the Olympiad

思路

可以用二分找，也可以直接用贪心数学

这里我用的贪心，将k个均匀的放在n行中，我们只需要看被分配最多凳子的那一行能分的最小长凳的长度即可

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n,m,k;cin>>n>>m>>k;int t=k/n;int mx=t;if(k%n) mx++;int x=m-mx;if(x<=0){cout<<m<<"\n";return;}int y=mx/(x+1);if(mx%(x+1)==0){cout<<y<<"\n";}else{cout<<y+1<<"\n";}}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}

E. Interesting Ratio

思路

我们发现合法的对数只能是（1 2）（2 4）（4 8）... （1 3）（2 6）（3 9）...（1 5）（2 10）...

发现都是（1*k 素数*k）k是任意正整数，这样统计就行了

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=1e7+10;
const int inf=1e18;
const int mod=998244353;vector<int> minp,primes;
void sieve(int n){minp.assign(n+1,0);primes.clear();for(int i=2;i<=n;i++){if(minp[i]==0){minp[i]=i;primes.push_back(i);}for(auto p:primes){if(i*p>n){break;}minp[i*p]=p;if(p==minp[i]){break;}}}
}
bool isprime(int n){return minp[n]==n;
}void solve(){int n;cin>>n;int cnt=0;for(int i=0;i<primes.size();i++){if(n<primes[i]) break;cnt+=(n/primes[i]);}cout<<cnt<<"\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);sieve(N);int _=1;cin>>_;while(_--) solve();return 0;
}

F. Igor and Mountain

思路

很明显此题是一个从最底层从下到上统计数量的动态规划dp的问题

用表示到达第i行第j列的方法数，此节点的dp值来源于下面一层到达此节点的方法，以及同层之间到达此节点的方法

那么我们便明确了状态转移方程，显然直接这样遍历是复杂度很高的

我们需要优化一下，根据d我们可以缩短枚举的范围，因为我们更新的时候加的是一段区间内的总和，又可以用前缀和优化

代码

#include<bits/stdc++.h>
using namespace std;#define vcoistnt ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 
#define int long long
#define vi vector<int>
#define vb vector<bool>
typedef pair<int,int> pll;const int N=2e5+10;
const int inf=1e18;
const int mod=998244353;void solve(){int n,m,d;cin>>n>>m>>d;vector<vi> dp(n+10,vi(m+10));   //第i行第j列的数量vector<vector<char>> s(n+10,vector<char>(m+10));bool b=false;for(int i=1;i<=n;i++){bool f=false;for(int j=1;j<=m;j++){cin>>s[i][j];if(s[i][j]=='X'){f=true;}}if(!f) b=true;}if(b){cout<<"0\n";return;}int xd=sqrt(d*d-1);     //上面一个点能从下面到的区间for(int i=n;i>=1;i--){vi tmp(m+1,0);    //表示第i行某个节点 从下面一行到此节点 的数量vi predp(m+10,0);   //表示上一层dp的前缀和vi pretmp(m+10,0);  //表示本层tmp的前缀和if(i==n){for(int j=1;j<=m;j++){if(s[i][j]=='X') tmp[j]=1;}}else{for(int j=1;j<=m;j++){predp[j]=(predp[j-1]+dp[i+1][j])%mod;}for(int j=1;j<=m;j++){if(s[i][j]=='X'){// 尝试暴力更新tmp的值// for(int k=max(j-xd,1ll);k<=min(j+xd,m);k++){//     if(s[i+1][k]=='X'){//         tmp[j]=(tmp[j]+dp[i+1][k])%mod;//     }// }tmp[j]=(tmp[j]+predp[min(j+xd,m)]-predp[max(j-xd,1ll)-1]+mod)%mod;}}}for(int j=1;j<=m;j++){pretmp[j]=(pretmp[j-1]+tmp[j]%mod);}for(int j=1;j<=m;j++){if(s[i][j]=='X'){// 尝试暴力更新灯dp的值// for(int k=max(j-d,1ll);k<=min(j+d,m);k++){//     if(s[i][k]=='X')//     dp[i][j]=(dp[i][j]+tmp[k])%mod;// }dp[i][j]=(dp[i][j]+pretmp[min(j+d,m)]-pretmp[max(j-d,1ll)-1]+mod)%mod;}}}int ans=0;for(int i=1;i<=m;i++){ans=(ans+dp[1][i])%mod;}cout<<ans%mod<<"\n";
}
signed main() {vcoistntcout<<fixed<<setprecision(2);int _=1;cin>>_;while(_--) solve();return 0;
}