A-3的倍数
首先求出sum,如果sum为3的倍数,那么直接可以降序
如果sum%3=1,那么优先删除一个对3取模余1的数,如果没有则删除两个对3取模余2的数
如果sum%3=2,那么优先删除一个对3取模余2的数,如果没有则删除两个对3取模余1的数
trick:
1.不是很好写,要想从vector里删除数,挺麻烦的,还要考虑越界,可以先标记要删除的数,比如值标记为-1,然后将不是-1的都放到一个新的容器里,就相当于删除了标记的数2.对3取模,结果只有3种,情况很少,分别讨论即可
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+10;
int a[N];
int n;
void solve() {
cin>>n;
map<int,int>mp;
int sum=0;
vector<int>ans;
for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]%3]++,sum+=a[i];
sort(a+1,a+1+n);
if(sum%3==0){
for(int i=1;i<=n;i++) ans.push_back(a[i]);
}
else if(sum%3==1){
if(mp[1]){
for(int i=1;i<=n;i++){
if(a[i]%3==1){
a[i]=-1;
break;
}
}
for(int i=1;i<=n;i++){
if(a[i]==-1) continue;
ans.push_back(a[i]);
}
}
else if(mp[2]>=2){
int cnt=2;
for(int i=1;i<=n;i++){
if(a[i]%3==2&&cnt){
a[i]=-1;
cnt--;
}
}
for(int i=1;i<=n;i++){
if(a[i]==-1) continue;
ans.push_back(a[i]);
}
}
}
else{
if(mp[2]){
for(int i=1;i<=n;i++){
if(a[i]%3==2){
a[i]=-1;
break;
}
}
for(int i=1;i<=n;i++){
if(a[i]==-1) continue;
ans.push_back(a[i]);
}
}
else if(mp[1]>=2){
int cnt=2;
for(int i=1;i<=n;i++){
if(a[i]%3==1&&cnt){
a[i]=-1;
cnt--;
}
}
for(int i=1;i<=n;i++){
if(a[i]==-1) continue;
ans.push_back(a[i]);
}
}
}
if(ans.size()==0){
cout<<-1<<endl;
return;
}
reverse(ans.begin(),ans.end());
if(ans[0]==0) cout<<0<<endl;
else{
for(auto v:ans) cout<<v;
cout<<endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}
B-午餐的品格
很容易得到,答案为 2 n 2^n 2n-1- C n x C_{n}^{x} Cnx-$C_{n}^{y} − - −C_{n}^{z} $
2 n 2^n 2n需要用快速幂求解,快速幂的时间复杂度为log(n)
但是,n达1e9,如何求那么大的组合数,所幸x,y,z最多2e5
C n m C_{n}^{m} Cnm=$\frac{(n-m+1) * (n-m+2) * …*n }{1 * 2 *… * m} $
求分子最多枚举2e5次,求分母最多枚举2e5次
最后要注意防止答案为负数的处理方式:
ans=(ans%mod+mod)%mod;
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+10,mod=1e9+7;
int fac[N];
int n,x,y,z;
int qmi(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int C(int n,int m){
if(n<m) return 0;
int res=1;
for(int i=n-m+1;i<=n;i++) res=res*i%mod;
return res*qmi(fac[m],mod-2)%mod;
}
void solve() {
cin>>n>>x>>y>>z;
fac[0]=1;
for(int i=1;i<=2e5;i++){
fac[i]=fac[i-1]*i%mod;
}
int ans=qmi(2,n)-1;
ans-=C(n,x);
ans-=C(n,y);
ans-=C(n,z);
ans=(ans%mod+mod)%mod;
cout<<ans<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
while(t--) {
solve();
}
return 0;
}
G-fsl 的背包
思维难度挺大的,虽说题目名字是背包,但是不符合经典的背包,所以不是背包问题
容易想到将所有物品按照价值从小到大排序,然后枚举每件物品作为中位数,在它的前面取k/2件体积最小的,在它的后面取k/2件体积最小的,check是否总体积超过m,如果不超过,那么作为预选答案,取最大的答案
问题在于如何快速求出该件物品前面取k/2件最小的体积之和,可以利用大根堆,将前面的物品依次放入大根堆中,然后维护元素个数为k/2
后面的物品同理
while(q.size()>k/2) sum-=q.top(),q.pop();
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e6+10;
int n,m,k;
struct node{
int w,v;
bool operator<(const node &W)const{
if(v==W.v) return w<W.w;
return v<W.v;
}
}q[N];
int pre[N],last[N];
void solve() {
cin>>n>>m>>k;
memset(pre,0,sizeof pre);
memset(last,0,sizeof last);
for(int i=1;i<=n;i++) cin>>q[i].w;
for(int i=1;i<=n;i++) cin>>q[i].v;
sort(q+1,q+1+n);
k/=2;
priority_queue<int>heap1;
int sum=0;
for(int i=1;i<=n;i++){
sum+=q[i].w;
heap1.push(q[i].w);
while(heap1.size()>k){
sum-=heap1.top();
heap1.pop();
}
pre[i]=sum;
}
priority_queue<int>heap2;
sum=0;
for(int i=n;i>=1;i--){
sum+=q[i].w;
heap2.push(q[i].w);
while(heap2.size()>k){
sum-=heap2.top();
heap2.pop();
}
last[i]=sum;
}
int ans=-1;
for(int i=k+1;i+k<=n;i++){
if(pre[i-1]+last[i+1]+q[i].w<=m) ans=max(ans,q[i].v);
}
cout<<ans<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
while(t--) {
solve();
}
return 0;
}
K-简单游戏
只有赢和输两种情况,要么赢要么输,没有平局
如果一开始的局面先手会输的话,那么先手就把1删掉,把这一局面抛给后手,所以先手必胜
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n;
void solve() {
cin>>n;
cout<<"ocharin"<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve()
}
return 0;
}