复习3-2：习题篇：

3.

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf =0x3f3f3f3f;
int a[1100][1100];
int b[1100][1100][4];
int n,m,q;
int dfs(int i,int j,int q)
{if(i<=0||j<=0||i>n||j>m||q<0)return INT64_MIN;if(i==n&&j==m)return a[i][j];if(b[i][j][q])return b[i][j][q];int ma=0;if(__gcd(a[i][j],a[i][j+1])==1)ma=1;int aa=dfs(i,j+1,q-ma);int mb=0;if(__gcd(a[i][j],a[i+1][j])==1)mb=1;int bb=dfs(i+1,j,q-mb);int cn=a[i][j]+max(aa,bb);b[i][j][q]=cn;return cn;
}
void solve()
{cin>>n>>m>>q;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}int ans=dfs(1,1,q);ans=ans<=0?-1:ans;cout<<ans;
}
signed main()
{ios_base::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int t;t=1;//cin>>t;while(t--){solve();}return 0;
}

4.

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf =0x3f3f3f3f;
const int mod=1e9+7;
int counting(int a,int b)
{int result=1;while(b){if(b&1){result=result*a%mod;b/=2;a=a*a%mod;}else{b/=2;a=a*a%mod;}}return result;
}
void solve()
{int n,a,cn=0,odd=0,even=0;cin>>n;for(int i=0;i<n;i++){cin>>a;cn+=a;if(a&1)odd++;else even++;}if(cn&1){cout<<0<<endl;return ;}else{int sum1=counting(2,odd-1);if(odd==0)sum1=1;int sum2=counting(2,even);cout<<sum1*sum2%mod<<endl;}
}
signed main()
{ios_base::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int t;//t=1;cin>>t;while(t--){solve();}return 0;
}

5.B-小红的因子数_牛客周赛 Round 31 (nowcoder.com)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3e4+5;
const int inf=0x3f3f3f3f;
map<int,int>mp;
void solve()
{int x;cin>>x;if(x==1){cout<<0;return ;}for(int i=2;i*i<=x;i++){while(x%i==0){mp[i]++;x/=i;}}if(x!=1)mp[x]++;cout<<mp.size();
}
signed main()
{ios_base::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);solve();return 0;
}

6.E-小红构造数组_牛客周赛 Round 29 (nowcoder.com)

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf =0x3f3f3f3f;
typedef pair<int,int> pii;
int a[N];
map<int ,int>mp;
void solve()
{int x;cin>>x;if(x==1){cout<<-1;return ;}for(int i=2;i*i<=x;i++){while(x%i==0){mp[i]++;x/=i;}}if(x!=1)mp[x]++;vector<int>ve;while(!mp.empty()){int a=-1,b=0;for(auto[x,y]:mp){if(!ve.empty()&&x==ve.back())continue;if(y>b){a=x,b=y;}}if(a==-1){cout<<-1;return ;}ve.push_back(a);mp[a]--;if(mp[a]==0)mp.erase(a);}cout<<ve.size()<<endl;for(auto i:ve){cout<<i<<' ';}
}
signed main()
{ios_base::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int t;t=1;//cin>>t;while(t--){solve();}return 0;
}

倒计时64天-CSDN博客

7.

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf =0x3f3f3f3f;
typedef pair<int,int> pii;
void solve()
{int n,ans1=2,ans2=2;cin>>n;set<pii>se;for(int i=0;i<n;i++){int x,y;cin>>x>>y;se.insert({x,y});if(y<=0)ans1=1;if(y>=0)ans2=1;}for(auto[x,y]:se){for(int i=-1;i<=1;i++){if(se.count({x^3,y+i})){if(y<0)ans1=0;if(y>0)ans2=0;}}}int ans=3-se.count({1,-1})-se.count({1,1})-se.count({2,0});cout<<min(ans,ans1+ans2)<<endl;
}
signed main()
{ios_base::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int t;//t=1;cin>>t;while(t--){solve();}return 0;
}

8.

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf =0x3f3f3f3f;
int a[N],b[N];
void solve()
{int n,q,t;cin>>n>>q>>t;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+1+n);for(int i=1;i<=n;i++){b[i]=b[i-1]+a[i];}while(q--){int m;cin>>m;int r=m/t;if(r>=n)cout<<t<<endl;else{cout<<b[n-r]+t<<endl;}}
}
signed main()
{ios_base::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int t;t=1;//cin>>t;while(t--){solve();}return 0;
}

9.

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf =0x3f3f3f3f;
struct node{int aa,bb,cc;
}a[N];
bool cmp(node l,node r)
{return l.aa<r.aa;
}
void solve()
{int n,m,sum=-inf;cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i].aa>>a[i].bb;}sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++){a[i].bb+=a[i-1].bb;a[i].aa-=a[i].bb;if(a[i].aa<=m){sum=max(sum,a[i].bb+m);}}if(sum<=0)cout<<m<<endl;else cout<<sum<<endl;
}
signed main()
{ios_base::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int t;//t=1;cin>>t;while(t--){solve();}return 0;
}

10.

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+6;
const int inf =0x3f3f3f3f;
int n,m,a[11],u[11],v[11],ans;
void dfs(int x)
{if(x==m+1){int t=0;for(int i=2;i<=n;i++){if(a[1]<a[i])t++;}ans=min(ans,t+1);return ;}a[u[x]]+=3,dfs(x+1),a[u[x]]-=3;a[v[x]]+=3,dfs(x+1),a[v[x]]-=3;a[u[x]]++,a[v[x]]++,dfs(x+1),a[u[x]]--,a[v[x]]--;
}
void solve()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>u[i]>>v[i];}ans=n+1;dfs(1);cout<<ans<<endl;
}
signed main()
{ios_base::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);int t;//t=1;cin>>t;while(t--){solve();}return 0;
}