noi-2025年12月16号作业

题目：B4407 [语言月赛 202509] 逃避讲题的最好方法是：

网址：https://www.luogu.com.cn/problem/B4407

思路：我们分别使用mx、mn数组记录每一道题的最大值分数和最小分数，同时使用一个e数组来保存每一道题的分数。首先特判，如果人数小于等于2的话，一定要上台，然后我们记录一下要改变的次数并贪心地修改分数，如果需要改变的次数大于c的话，那么就一定要上台。最后，我们判断一下改的是否合格。

知识点：set的使用，思维题

代码:

#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pss pair<string,string> #define fi first #define se second #define pb push_back #define eb emplace_back using namespace std; const int maxn=3e3+100; ll a[maxn][maxn]; int n,m,s; ll mx[maxn],mn[maxn]; set<int>e[maxn]; void solve() { cin>>n>>m>>s; for(int i=1;i<=m;i++) { mx[i]=-1; mn[i]=1e17; e[i].clear(); } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; mx[j]=max(mx[j],a[i][j]); mn[j]=min(mn[j],a[i][j]); } } for(int j=1;j<=m;j++) { for(int i=1;i<=n;i++) { e[j].insert(a[i][j]); } } int c; cin>>c; if(n<=2) { cout<<"up"<<'\n'; return; } int need=0; for(int i=1;i<=m;i++) { if(a[s][i]!=mx[i]&&a[s][i]!=mn[i]) continue; if(e[i].size()==1) { cout<<"up"<<'\n'; return; } if(a[s][i]==mx[i]) { auto it=e[i].begin(); a[s][i]=(*it)+1; }else{ auto it=e[i].end(); it--; a[s][i]=(*it)-1; } need++; } for(int i=1;i<=m;i++) { mx[i]=-1; mn[i]=1e17; } if(need>c) { cout<<"up"<<'\n'; return; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { mx[j]=max(mx[j],a[i][j]); mn[j]=min(mn[j],a[i][j]); } } for(int i=1;i<=m;i++) { if(a[s][i]==mx[i]||a[s][i]==mn[i]) { cout<<"up"<<'\n'; return; } } cout<<"down"<<'\n'; } int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int _; cin>>_; while(_--) solve(); return 0; }

题目：P1029 [NOIP 2001 普及组] 最大公约数和最小公倍数问题

网址：https://www.luogu.com.cn/problem/P1029

思路：首先，如果y%x!=0的话，那么答案一定为0。接着我们分别对x和y进行质数分解，如果对于对一个质数，x和y的次数不相等的话，那么就有两种可能。

知识点：求质数，质数分解

代码:

#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pss pair<string,string> #define fi first #define se second #define pb push_back #define eb emplace_back using namespace std; const int maxn=2e5+100; ll a[maxn],cnt; int n,m; bool is_pri(ll x) { for(int i=2;i*i<=x;i++) { if(x%i==0) return false; } return true; } void solve() { ll x,y; cin>>x>>y; if(y%x!=0) { cout<<0; return; } for(int i=2;i<=100000;i++) { if(is_pri(i)) { a[++cnt]=i; } } ll ans=1; for(int i=1;i<=cnt;i++) { ll cnt1=0,cnt2=0; while(x%a[i]==0) { x/=a[i]; cnt1++; } while(y%a[i]==0) { cnt2++; y/=a[i]; } if(cnt1!=cnt2) { ans=ans*2; } } cout<<ans<<'\n'; } int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int _=1; // cin>>_; while(_--) solve(); return 0; }

题目：P14566 【MX-S12-T1】取模

网址：https://www.luogu.com.cn/problem/P14566

思路：把p从非常大的值一路减小，会发现其实就是对a数组进行压缩。

知识点：思维题

代码:

#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pss pair<string,string> #define fi first #define se second #define pb push_back #define eb emplace_back using namespace std; const int maxn=2e5+100; ll a[maxn]; int n,m; void solve() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } sort(a+1,a+1+n); if(a[n]==0) { cout<<0<<'\n'; return; } ll v1=a[n]-a[1]; for(int i=1;i<=n;i++) { a[i]=a[i]%a[n]; } sort(a+1,a+1+n); ll v2=a[n]-a[1]; cout<<max(v1,v2)<<'\n'; } int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int _=1; cin>>_; while(_--) solve(); return 0; }

题目：P12817 [NERC 2021] Deletive Editing

网址：https://www.luogu.com.cn/problem/P12817

思路：我们先从s中找到t，然后再判断一下能否合法删除

知识点：思维题

代码:

#include<bits/stdc++.h> #define ll long long #define pii pair<int,int> #define pss pair<string,string> #define fi first #define se second #define pb push_back #define eb emplace_back using namespace std; const int maxn=2e5+100; ll a[maxn]; int n,m; string s,t; int vis[maxn]; void solve() { cin>>s>>t; if(s==t) { cout<<"YES"<<'\n'; return; } reverse(s.begin(),s.end()); reverse(t.begin(),t.end()); int last=-1; int len=s.length(); for(int i=0;i<len;i++) { vis[i]=0; } for(auto ch1:t) { bool ok=false; for(int i=last+1;i<len;i++) { if(s[i]==ch1) { ok=true; vis[i]=1; last=i; break; } } if(!ok) { cout<<"NO"<<'\n'; return; } } map<char,int>p; for(int i=0;i<len;i++) { if(vis[i]) { if(p[s[i]]) { cout<<"NO"<<'\n'; return; } }else{ p[s[i]]=1; } } cout<<"YES"<<'\n'; } int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int _=1; cin>>_; while(_--) solve(); return 0; }