A
枚举m到2e5为因数，期间更新最大公因数。
int n, m; cin>>n>>m;
vector<pair<int,int>> ans;
unordered_map<int,int> mp;
for(int i=0;i<n;i++){
int x; cin>>x;
mp[x]++;
}
for(int i=m;i<=2e5;i++){
int sum=0, num=0;
for(int j=i;j<=2e5;j+=i){
if(mp.count(j)){
sum+=mp[j];
num=__gcd(num,j);
}
}
if(sum>1){
ans.emplace_back(sum,num);
}
}
sort(ans.begin(),ans.end(),[&](auto p1, auto p2){
if(p1.first==p2.first) return p1.second<p2.second;
return p1.first>p2.first;
});
if(ans.size()){
cout<<ans[0].first<<" "<<ans[0].second<<"\n";
} else cout<<"0 0\n";
B
手推一下，枚举最终答案，要想x成立，b数组中不能有x，则原数组中的子数组中，x要被夹在1，2，，，x-1中，例：x=4， 则子数组 1，4，3，2 成立，而4，2，1，3就不成立。
int n; cin>>n;
vector<int> v(n), ind(n);
for(int i=0;i<n;i++){
cin>>v[i]; v[i]--;
ind[v[i]]=i;
}
if(n==1){
cout<<"1\n";
return 0;
}
int l=ind[0], r=ind[1];
if(l>r) swap(l,r);
for(int i=2;i<n;i++){
if(ind[i]>l&&ind[i]<r){
cout<<i+1<<"\n";
return 0;
}
l=min(l,ind[i]);
r=max(r,ind[i]);
}
cout<<n+2<<"\n";
C
int T, H, t, n; cin>>T>>H>>t>>n;
if(H*t>=T*n) cout<<"kirito\n";
else cout<<"hangeki\n";
D
从终点开始倒着循环，注意方向。
int n, m; cin>>n>>m;
vector<vector<int>> v(n,vector<int>(m)), ans(n,vector<int>(m,-1)), dir={{0,-1},{-1,0},{0,1},{1,0}};
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
char c; cin>>c;
if(c=='L') v[i][j]=0;
else if(c=='R') v[i][j]=2;
else if(c=='U') v[i][j]=1;
else v[i][j]=3;
}
}
int a=n-1, b=m-1, c=0;
while(1){
ans[a][b]=c;
int x=a+dir[(v[a][b]+2)%4][0], y=b+dir[(v[a][b]+2)%4][1];
if(x<0||x>=n||y<0||y>=m) break;
if(ans[x][y]!=-1) break;
a=x, b=y, c+=1;
}
for(auto& it:ans){
for(auto& _it:it){
cout<<_it<<' ';
}
cout<<'\n';
}
E
待补
F
加分就打，不加分就不打。
int x, n; cin>>x>>n;
vector<int> v(n);
for(int i=0;i<n;i++) cin>>v[i];
for(int i=0;i<n;i++){
if(v[i]>x){
x+=(v[i]-x)/2;
}
}
cout<<x<<"\n";
G
待补
H
一开始还以为二分加01背包呢，复杂度太爆炸了。只是一个单纯的二分从小到大拿。
int n, s; cin>>n>>s;
vector<int> v(n), ans(n+1);
for(int i=0;i<n;i++) cin>>v[i];
auto check=[&](int k){
vector<int> _v=v;
for(int i=0;i<n;i++) _v[i]+=k*(i+1);
sort(_v.begin(),_v.end());
int sum=0;
for(int i=0;i<k;i++){
sum+=_v[i];
if(sum>s){
return 0;
}
}
ans[k]=sum;
return 1;
};
int l=0, r=n+1, mid;
while(l+1<r){
mid=(l+r)>>1;
if(check(mid)) l=mid;
else r=mid;
}
cout<<l<<" "<<ans[l]<<"\n";
I
具体没有证明，手推了一下，例如：x=7，先拿1，后拿6；先拿2，后那5；先拿3，后拿4。所以只要先手拿不完，后手必赢。
int n; cin>>n;
if(n==1) cout<<"Dbqjubmjtn\n";
else cout<<"Tpdjbmjtn\n";
J
假做法： 每一位存下后面最近的大于自身和小于自身的下标。每次确定最区间，右区间跳跃过最大值和最小值相同的个数。例如：5 2 4 3 1。一开始l=0， r=1，跳过中间2，3，直接跳到最小值发生变化的4。
后面理解了仔细点挺好写的。主要是前面后面最近的大于自身和小于自身的下标不好找，开始卡了好久，又来想到用set（其实priority_queue也可以）。对小于自身的数组：从大往小更新过去未更新的数。同理，对大于自身的数组：从小往大更新过去未更新的数。
这种做法的最坏时间复杂度是n*n，但是可以过，这道题可能数据有点弱。例如：1，2，3，4，5.
真做法还不会。
int n; cin>>n;
set<int> sti, sta;
vector<int> v(n), ind(n), mi(n,n), ma(n,n);
for(int i=0;i<n;i++){
cin>>v[i];
v[i]--;
ind[v[i]]=i;
}
if(n==1){
cout<<0<<"\n";
return 0;
}
for(int i=0;i<n;i++){
while(sti.size()){
int x=*sti.rbegin();
if(x>v[i]){
mi[ind[x]]=i;
sti.erase(x);
} else break;
}
while(sta.size()){
int x=*sta.begin();
if(x<v[i]){
ma[ind[x]]=i;
sta.erase(x);
} else break;
}
sti.insert(v[i]);
sta.insert(v[i]);
}
int ans=0, mod=998244353;
for(int i=0;i+1<n;i++){
int idmi=i, idma=i+1;
if(v[idmi]>v[idma]) swap(idmi,idma);
ans=(ans+mod+idma-idmi)%mod;
while(1){
if(mi[idmi]<ma[idma]){
ans=(ans+mod+(mi[idmi]-max(idma,idmi)-1)*(idma-idmi))%mod;
idmi=mi[idmi];
ans=(ans+mod+idma-idmi)%mod;
} else if(mi[idmi]>ma[idma]){
ans=(ans+mod+(ma[idma]-max(idma,idmi)-1)*(idma-idmi))%mod;
idma=ma[idma];
ans=(ans+mod+idma-idmi)%mod;
} else{
ans=(ans+mod+(n-max(idma,idmi)-1)*(idma-idmi))%mod;
break;
}
}
}
cout<<ans<<"\n";
K
和J题一样的思路，一个大减小，一个绝对值，都是假做法。 按理说两题基本上一模一样，为啥k只有4个人过？
int n; cin>>n;
set<int> sti, sta;
vector<int> v(n), ind(n), mi(n,n), ma(n,n);
for(int i=0;i<n;i++){
cin>>v[i];
v[i]--;
ind[v[i]]=i;
}
if(n==1){
cout<<0<<"\n";
return 0;
}
for(int i=0;i<n;i++){
while(sti.size()){
int x=*sti.rbegin();
if(x>v[i]){
mi[ind[x]]=i;
sti.erase(x);
} else break;
}
while(sta.size()){
int x=*sta.begin();
if(x<v[i]){
ma[ind[x]]=i;
sta.erase(x);
} else break;
}
sti.insert(v[i]);
sta.insert(v[i]);
}
int ans=0, mod=998244353;
for(int i=0;i+1<n;i++){
int idmi=i, idma=i+1;
if(v[idmi]>v[idma]) swap(idmi,idma);
ans=(ans+mod+abs(idma-idmi))%mod;
while(1){
if(mi[idmi]<ma[idma]){
ans=(ans+mod+(mi[idmi]-max(idma,idmi)-1)*abs(idma-idmi))%mod;
idmi=mi[idmi];
ans=(ans+mod+abs(idma-idmi))%mod;
} else if(mi[idmi]>ma[idma]){
ans=(ans+mod+(ma[idma]-max(idma,idmi)-1)*abs(idma-idmi))%mod;
idma=ma[idma];
ans=(ans+mod+abs(idma-idmi))%mod;
} else{
ans=(ans+mod+(n-max(idma,idmi)-1)*abs(idma-idmi))%mod;
break;
}
}
}
cout<<ans<<"\n";
L
每个h存下后面距离最近的a和n，同理，每个t存下后面距离最近的e和n。遍历到每个h和t就尝试删掉。
int n; cin>>n;
string s; cin>>s;
vector<int> v(n,n);
int _n=n, _a=n, _e=n;
for(int i=n-1;i>=0;i--){
if(s[i]=='n') _n=i;
else if(s[i]=='a'){
_a=i;
v[i]=_n;
} else if(s[i]=='e'){
_e=i;
v[i]=_n;
} else if(s[i]=='h'){
v[i]=_a;
} else if(s[i]=='t'){
v[i]=_e;
}
}
int ans=n;
for(int i=0;i<n;i++){
if(v[i]!=n&&v[v[i]]!=n){
if(s[i]=='h'||s[i]=='t'){
ans=min(ans,v[v[i]]-i-2);
}
}
}
cout<<(ans==n?-1:ans)<<"\n";
M
要不去查查自己学校校训？
cout<<"我不知道\n";
`
京公网安备 11010502036488号