xp04 - 考试题 day01
2025-08-13 09:44:19
发布于：浙江
16阅读
0回复
0点赞
竞赛日期
/*题意：给了n个数字，求最少能用前几个数字组成
01032025*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
long long a[N] , dp[N];
//记录每一个数字出现了几次
long long cnt[N];//每个数字出现几次
int main(){
int t;
cin >> t;
while(t--){
int n;
cin >> n;
for(int i = 1 ; i <= n ; i ++){
cin >> a[i];
}
int flag = 0;
for(int i = 1 ; i <= n ; i ++){
cnt[a[i]]++;
if(cnt[0] >= 3 && cnt[1] >= 1 && cnt[2] >= 2 && cnt[3] >= 1 && cnt[5] >= 1){
cout << i << endl;
flag = 1;
break;
}
}
if(flag == 0){
cout << 0 << endl;
}
for(int i = 0 ; i <= 10; i ++){
cnt[i] = 0;
}
}
}
以23结尾
#include<bits/stdc++.h>
using namespace std;
int n,m,a[200010],s[200010];
// s数组 统计 [1,i] 以23结尾
int main(){
cin>>n>>m;
// 123 % 100 = 23
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]%100==23)s[i] = s[i-1] + 1;
else s[i] = s[i-1];
}
while(m--){
int l,r;
cin>>l>>r;
cout<<s[r]-s[l-1]<<" ";
}
return 0;
}
逃离迷宫
#include <iostream>
#include <queue>
using namespace std;
struct node{
int x,y;
};
int n,m;
char map[50][50];
int vis[50][50];
int xn[6]={0,0,1,-1};
int yn[6]={1,-1,0,0};
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>map[i][j];
}
}
queue<node>q;
q.push({1,1});
vis[1][1]=1;
while(q.size()!=0){
node r=q.front();
q.pop();
if(r.x==n && r.y==m){
cout<<"YES";
return 0;
}
for(int i=0;i<4;i++){
int lx=xn[i]+r.x;
int ly=yn[i]+r.y;
if(lx>=1 && ly>=1 && lx<=n && ly<=m && map[lx][ly]!='#' && vis[lx][ly]==0){
vis[lx][ly]=1;
q.push({lx,ly});
}
}
}
cout<<"NO";
}
查找最终局
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000010];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
while(m--){
int x;
cin>>x;
int l = lower_bound(a+1,a+n+1,x)-a;//大于等于x的第一个位置
int r = upper_bound(a+1,a+n+1,x)-a;//大于x的第一个位置
if(l+4<=n && a[l+4]==x)cout<<l+4<<" ";
else cout<<-1<<" ";
if(r-2>=1 && a[r-2]==x)cout<<r-2<<" ";
else cout<<-1<<" ";
int sum = r-l;
cout<<sum<<endl;
}
return 0;
}
区区间
#include<bits/stdc++.h>
using namespace std;
long long a[100010];
int main(){
int t;
cin>>t;
while(t--){
long long n,k,x;// 目标总和
cin>>n>>k>>x;
long long sum = 0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
if(sum*k<x)cout<<0<<endl;
else{
//10 1 1 2 1 1 2 1 1 2
long long cnt = (x+sum-1)/sum;//至少需要多少个前缀和
long long now = cnt*sum;
long long ans = cnt*n;
for(int i=1;i<=n;i++){
if(now-a[i]<x)break;
now-=a[i];
ans--;
}
cout<<n*k-ans+1<<endl;
}
}
return 0;
}
排列缺失
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
vector<int> p(n + 1);
vector<int> vis(n + 1);
int ans = 0;
for(int i = 1; i <= n; i++)
cin >> p[i];
for(int i = 1; i <= n; i++) {
int x;
cin >> x;
while(!vis[p[x]]) { // 如果在前i - 1操作中第x个位置没有被重置为p[x] = x的情况
ans++; // 需要重置一次
vis[p[x]] = 1; // 标记第x个位置
x = p[x]; // 第x个位置变动后，可能会导致连锁变动的位置
}
cout << ans << " ";
}
cout << endl;
}
int main () {
int t;
cin >> t;
while(t--) solve();
}
吃寿司
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pir;
void solve() {
ll n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
ll sum = k;
priority_queue<int, vector<int>, greater<int>> q; // 小根堆
ll ans = 0;
for (int i = n - k; i >= 1; i--) {
if (sum >= k) {
sum -= k;
q.push(a[i]);
ans += a[i];
} else {
if (!q.empty() && q.top() < a[i]) {
ans -= q.top();
q.pop();
q.push(a[i]);
sum++;
ans += a[i];
} else {
sum++;
}
}
}
cout << ans << "\n";
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
这里空空如也
有帮助，赞一个