A.签到:https://ac.nowcoder.com/acm/contest/86373/A
x=1,y=n-1即可,注意不合法:y<=0或者x==y。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int z;
int main(){
cin>>z;
int x=1,y=z-1;
if(x==y) cout<<"NO";
else cout<<"YES"<<endl<<x<<" "<<y;
}
B.贪心:https://ac.nowcoder.com/acm/contest/86373/B
注意不一定要把a,b用完。我们只要尽可能让a把n变成3的倍数并尽可能的小即可。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
long long t,a,b,n;
int main(){
cin>>t;
while(t--){
cin>>a>>b>>n;
if(a>=n){
cout<<"YES"<<endl;
continue;
}
n-=a;
for(int i=1;i<=a;i++){
if(n%3==0) break;
n++;
}
if(n%3){
cout<<"NO"<<endl;
continue;
}
long long k=n/3*2;
if(b>=k) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
C贪心.https://ac.nowcoder.com/acm/contest/86373/C
有两个一样的正数(包括0,0也只有用负数或者自己消去,与正数同一个性质)就直接消,剩下的我们看看正数与负数的数量分类讨论即可。
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
int a[100010],n;
int cnt1,cnt2,ans;//1:+
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int k=n;
for(int i=1;i<=n-1;i++){
if(a[i]<0) cnt2++;
if(a[i]==a[i+1]&&a[i]>=0){
k-=2;
i++;
}
}
cnt1=k-cnt2;
if(cnt1>=cnt2) cout<<cnt1-cnt2;
else cout<<abs(cnt1-cnt2)%2;
}
D优先队列。https://ac.nowcoder.com/acm/contest/86373/D
不难看出:我们把每一个数字最高位的max即可。但是万一有相等?我们应该选哪个?
如15,12,显然我们应该先用15的1。156,157,因为我们希望7尽可能早的出来,于是我们先出1,变成57,此时显然选5再选7。因此我们感性的推断:我们把字符串放入优先队列,每次取max的头。
正确性怎么证明?这里我们考虑只有两个数的情况,这样>=3的两两对比也就知道了。
假如afbc,afb1c(b<b1),若取afbc的a,我们不妨令它推出的最优解axyzb...b1,那么我们只要说明可以得到axyzb1....就可以得证。
事实上我们不考虑b/b1后面的数,因为前面一定相同(axyz一定在b和b1的前面),因此我们不妨把b1按照b的流程对称走一遍就可以得到更优解。证毕!
下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 998244353
#define N 200000
int i,j,k,n,m,t,d,mn,fa[N+50],a[N+50];
string s,res;
priority_queue<string> q;
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n;
for(i=1;i<=n;i++){
cin>>s;
q.push(s);
}
while(!q.empty()){
string s=q.top();
q.pop();
res+=s[0];
s.erase(0,1);
if(s!=""){
q.push(s);
}
}
cout<<res;
}
E。带权并查集:https://ac.nowcoder.com/acm/contest/86373/E
维护好每个并查集中的max,排个序加起来即可,下面是AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
ll a[100010];
int fa[100010];
ll zhi[100010];
ll w[100010];
int cnt=1;
vector<int> edge[100010];
int find(int x){
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y){
zhi[find(y)]=max(zhi[find(y)],zhi[find(x)]);
fa[find(x)]=find(y);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=n;i++) zhi[i]=a[i];
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
merge(u,v);
}
ll ans=0;
for(int i=1;i<=n;i++){
if(fa[i]==i){
w[cnt]=zhi[i];
cnt++;
}
}
sort(w+1,w+cnt);
for(int i=2;i<=cnt-1;i++){
ans+=w[i];
}
cout<<ans;
}
F。数学:https://ac.nowcoder.com/acm/contest/86373/F
对于一般的括号序列合法:1.左右括号相等 2.任何时间左括号>=右括号。
而这里的序列要求1即可。
我们令a为左括号数,b为右括号数,c为问号数(c1个变(,c2个变))。
易得:a+b+c=n,c1+c2=c,c1+a=b+c2
解得:c1=n/2-a。
加个组合数即可。
下面是AC代码:
#include<bits/stdc++.h>
#define endl "\n"
#define int long long
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 5;
int n;
string s;
int fac[maxn];
int quickPow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) ans = (ans * a) % mod;
b >>= 1;
a = (a * a) % mod;
}
return ans;
}
int inv(int x)
{
return quickPow(x, mod - 2);
}
void init() {
//求阶乘
fac[0] = 1;
for (int i = 1; i <=n; i++) {
fac[i] = fac[i - 1] * i % mod;
}
}
int C(int n, int m) {
init();
if(n<m||m<0)return 0;
return fac[n] * inv(fac[n-m]) % mod * inv(fac[m]) % mod;
}
void solve()
{
cin >> n;
cin >> s;
if(n%2==1)
{
cout<<0<<endl;
return;
}
int cnt1 = 0;
int cnt2 = 0;
for (int i = 0; i < n; i++)
{
if (s[i] == '?')cnt1++;
else if (s[i] == '(')cnt2++;
}
int t = n / 2 - cnt2;
if (t < 0)
{
cout << 0 << endl;
return;
}
int ans = C(cnt1, n / 2 - cnt2);
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
solve();
return 0;
}