牛客周赛 Round 42

小红叕战小紫

#include "bits/stdc++.h"
using namespace std;#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO  cout<<"No"<<endl;
#define pb(x) push_back(x);
#define fi first
#define sc second
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }void solve()
{string s;cin>>s;if(s.size()>1){cout<<"kou";}else {cout<<"yukari";}
}signed main()
{IOSint t;t=1;//cin>>t;while(t--){solve();}
}

小红的数组移动

#include "bits/stdc++.h"
using namespace std;#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO  cout<<"No"<<endl;
#define pb(x) push_back(x);
#define fi first
#define sc second
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
const int mod=1e9+7;
void solve()
{int n;cin>>n;vi a(n);for (int i=0;i<n;i++){cin>>a[i];}string s;cin>>s;int len=s.size();int sum=0;int pos=0;for (int i=0;i<len;i++){if(s[i]=='R'){// cout<<i<<endl;if(pos!=n-1){pos++;sum+=a[pos];}else {sum+=a[pos];}}else {//cout<<pos<<endl;if(pos!=0){pos--;sum+=a[pos];}else {sum+=a[pos];}}}cout<<sum%mod;;
}signed main()
{IOSint t;t=1;//cin>>t;while(t--){solve();}
}

小红的素数合并

想要极差尽可能的小，在有偶数个数时，我们可以让首位相乘。

而在奇数时，我们可以空出最后一个数，因为相比空出中间那个数来说的话，最后一个数，不仅最小值变大了，而且最大值变小了。

#include "bits/stdc++.h"
using namespace std;#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO  cout<<"No"<<endl;
#define pb(x) push_back(x);
#define fi first
#define sc second
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
const int mod=1e9+7;
void solve()
{int n;cin>>n;vi a(n);for (int i=0;i<n;i++){cin>>a[i];}sort(all(a));int maxn=0,minn=1e18;if(n%2==0){for (int i=0;i<n/2;i++){a[i]*=a[n-i-1];maxn=max(maxn,a[i]);minn=min(minn,a[i]);}}else {for (int i=0;i<n/2;i++){a[i]*=a[n-i-2];maxn=max(maxn,a[i]);minn=min(minn,a[i]);}maxn=max(maxn,a[n-1]);minn=min(minn,a[n-1]);}cout<<maxn-minn;
}signed main()
{IOSint t;t=1;//cin>>t;while(t--){solve();}
}

小红的树上删边

树上问题熟悉的遍历树。当发现这个子树的联通块大小为偶数时，便可以切除一条边。

#include "bits/stdc++.h"
using namespace std;#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO  cout<<"No"<<endl;
#define pb(x) push_back(x);
#define fi first
#define sc second
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }const int N = 200010;
int e[N],ne[N],st[N],h[N];
int idx;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int ans=0;
int sz[N];
void dfs(int x){st[x]=1;sz[x]=1;for (int i=h[x];~i;i=ne[i]){int j=e[i];if(st[j]==0){dfs(j);sz[x]+=sz[j];}}if(x!=1 && sz[x]%2==0){ans++;}}
void solve()
{int n;cin>>n;memset(h,-1,sizeof h);for (int i=1;i<=n-1;i++){int x,y;cin>>x>>y;add(x,y),add(y,x);}if(n&1){cout<<-1<<endl;return ;}dfs(1);cout<<ans;}signed main()
{IOSint t;t=1;//cin>>t;while(t--){solve();}
}

小红的子序列求和

使用了组合数的思想。j可以视为第i个数在序列中的位置。除去自身的贡献之外。还有前面j个数和后面j-j-1个数的贡献，并将组合数预处理，字符串的每一个字符的贡献只需要在这次计算就可以了。

#include "bits/stdc++.h"
using namespace std;#define int long long 
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0);
#define all(x) x.begin(),x.end()
#define pi pair<int,int> 
#define vi vector<int>
#define si set<int> 
#define mi map<int,int>
#define mc map<char,int>
#define YES cout<<"Yes"<<endl;
#define NO  cout<<"No"<<endl;
#define pb(x) push_back(x);
#define fi first
#define sc second
#define is insert
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }const int INF =1e18;
const int N = 200010;
const int mod = 1e9+7;//字符串的子序列有多少个。
int c[1010][1010];
int pow1[1000];void init(){for (int i=0;i<=1000;i++){for (int j=0;j<=i;j++){if(j==0 || i==j){c[i][j]=1;}else{c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;}}}pow1[0]=1;for (int i=1;i<=1000;i++){pow1[i]=pow1[i-1]*10%mod;}
}void solve()
{int n,k;cin>>n>>k;string s;cin>>s;int ans=0;for (int i=0;i<n;i++){for (int j=0;j<k;j++){int tmp=(s[i]-'0');ans+=pow1[k-j-1]*tmp%mod*c[i][j]%mod*c[n-i-1][k-1-j]%mod;ans%=mod;}}cout<<ans;
}signed main()
{IOSinit();int t;t=1;//cin>>t;while(t--){solve();}
}