8.19学习记录 各种比赛的题目总结

好几天没写博客了，来个大的。

牛客小白月赛55

A-D都是很ez的,E题和B题写一下

B题
给定两个数，a，b问你满足a&c=b&c条件的最大c是多少

显然的一点是c的每一位取值应该是这样的
对于a和b的每一个二进制位，如果相等则c在此二进制位上取1

#include 
#define int long long 
using namespace std;
int a,b;
signed main()
{cin>>a>>b;int ans=0;for(int i=0;i<63;i++){if((a&1ll)==(b&1ll)) ans+=(1ll<<i);b>>=1;a>>=1;}cout<<ans<<endl;return 0;
}

E题
给定一棵树的每个点的价值h，h：以此节点为端点的最长链。
构造一棵合法的树。如果构造不出来就输出-1

在做的时候把题看飘了，看成构造一棵二叉树了，不仅题变难了而且还把我卡了

对于-1的情况
1.h最大值有多个
2.价值为h的节点个数必须小于等于价值为h-1的节点个数

构造过程：把每个点往自己的h+1节点处挂就好了。

#include 
using namespace std;
#define endl '\n'
const int N = 3e6+100;
int t,n;
struct node
{int id,h;bool operator<(const node &a)const{return h>a.h;}
}a[N];
vector<pair<int,int>>ans;
vector<int>v[N];
void init()
{for(int i=1;i<=n+10;i++)v[i].clear();ans.clear();
}
bool check()
{if(v[a[1].h].size()>=2)return 0;for(int i=1;i<=n;i++)if(v[i].size()>v[i-1].size())return 0;for(int i=2;i<=n;i++){if(v[a[i].h+1].size()==0)return 0;ans.push_back({v[a[i].h+1][0],a[i].id});if(v[a[i].h+1].size()>1)v[a[i].h+1].erase(v[a[i].h+1].begin());}return 1;
}
void out()
{if(check()){cout<<a[1].id<<endl;for(int i=0;i<(int)ans.size();i++)cout<<ans[i].first<<" "<<ans[i].second<<endl;}elsecout<<-1<<endl;
}
int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);for(cin>>t;t;t--){cin>>n;init();for(int i=1;i<=n;i++){cin>>a[i].h;a[i].id=i;v[a[i].h].push_back(a[i].id);}if(n==1){if(a[1].h>0)cout<<-1<<endl;else cout<<1<<endl;continue;}sort(a+1,a+n+1);out();}return 0;
}

那么如果题目真的让我们去构造一棵二叉树怎么办？

显然-1的策略变化了

每个点只能有两个子节点，所以num[h]>num[h+1]*2是不符合的情况？但是稍等一下，我们发现假如对于h为0的节点有5个，h为1的节点有2个，h为2的节点有1个，这种情况下还是有解的。但是不变的限制是对于价值为h的节点，它只能挂在比自己价值大的节点上。所以按照h从大到小，我们把价值大的节点空余位置保留下来设为res，当num[h]>num[h+1]*2时判断用光res是否能够满足，不能才是-1的情况。

#include 
using namespace std;
const int N = 3e5+100;
int num[N];
int cd[N];
vector <int> id[N];
int vis[N];
signed main()
{int t;ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);for(cin>>t;t;t--){int n;cin>>n;for(int i=0;i<=n;i++){id[i].clear();vis[i]=0;cd[i]=0;num[i]=0;}int maxx=0;for(int i=1,temp;i<=n;i++){cin>>temp;id[temp].push_back(i);num[temp]++;maxx=temp>maxx?temp:maxx;}bool falg=true;int res=0;for(int i=maxx-1;i>=0;i--){if(num[i]-res>num[i+1]*2||num[i]<num[i+1]){falg=false;break;}else if(num[i]>num[i+1]*2){res=res-(num[i]-num[i+1]*2);}res+=max(0,num[i+1]*2-num[i]);}if(!falg||num[maxx]!=1){cout<<-1<<'\n';continue;}cout<<id[maxx][0]<<'\n';for(int i=maxx-1;i>=0;i--){for(auto z:id[i]){if(vis[z])continue;vis[z]=1;bool falg2=0;for(int j=maxx;j>i;j--){for(auto x:id[j]){if(cd[x]<=1){cd[x]++;cout<<x<<" "<<z<<'\n';falg2=1;break;}}if(falg2)break;maxx=j-1;}}}}return 0;
}

C. Fighting Tournament

题意：n个人比赛，每次在最前面的两个人比，赢的人放在队首，输的人放在队尾。问你在前n轮比赛中第k个人赢了几次。

思路：循环模拟，显然是当比赛进行到力量值最大的人时就达到了稳定装填
然而需要特别注意的是在队首的情况，队首因为不用等待前方淘汰的人所以不会有额外的赢局判定。

#include 
#define ll long long
#define endl '\n'
#define fastio cin.tie(0); cout.tie(0);ios::sync_with_stdio(0);
using namespace std;const int N = 2e5+100;
int a[N];
int vis[N];
signed main()
{int t;for(cin>>t;t;t--){int n,q;cin>>n>>q;int pos=0;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]==n)pos=i;vis[i]=0;}int maxx=a[1];int cnt=0;int id=1;for(int i=2;i<=pos;i++){if(maxx<a[i]){maxx=a[i];vis[id]=cnt;cnt=1;id=i;}else{cnt++;}}/* for(int i=1;i<=n;i++){cout<for(int i=1;i<=q;i++){int num,k;cin>>num>>k;if(num==1){if(num==pos){cout<<max(0,k-pos+1)<<endl;}else{int ans=min(vis[num],k-num+1);cout<<max(0,ans)<<endl;}}else if(num==pos){cout<<max(0,k-pos+2)<<endl;}else{int ans=min(vis[num],k-num+2);cout<<max(0,ans)<<endl;}}}return 0;
}

emmmmmm，然后有个DP，
然后最近这一场的div2 abc都太简单了，写个D的解吧

D1. Xor-Subsequence (easy version)

给定一个数组a，问最长的序列满足：序列中a[i]^j

思路：我们看数据，a的范围是200，这点格外注意。

然后发现如果当前的位置往后再去对比400个，也就是200的两倍，一定是考虑到了所有的异或的可能情况，也就是确定了目前这个数的值域了，然后根据经典线性DP求LIS的方法去求解就好了。

#include 
#define int long long
#define endl '\n'
#define fastio cin.tie(0);cout.tie(0);ios::sync_with_stdio(0)
using namespace std;int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
int lcm(int a, int b) {return a * b / gcd(a, b);
}
const int N = 3e6+100;
int dp[N];
int a[N];
signed main()
{int t;fastio;for(cin>>t;t;t--){int n;cin>>n;for(int i=0;i<n;i++){cin>>a[i];}for(int i=0ll;i<n;i++)dp[i]=1ll;for(int i=0ll;i<n;i++){for(int j=i+1ll;j<=i+2000ll&&j<n;j++){if((a[j]^i)>(a[i]^j)){dp[j]=max(dp[j],dp[i]+1ll);}}}int maxx=0;for(int i=0;i<n;i++){maxx=max(dp[i],maxx);}cout<<maxx<<'\n';}return 0;
}

牛客多校：加赛J题

题意：给定一个只包含0 1 2的顺时针循环数组，既n的下一项是1。如果第i+1项是(a[i]+1)%3，则可以把第i项变成第i+1项。

思路：

#include 
using namespace std;
const int N = 1e6+100;
int a[N];
int vis[3];
int main()
{int t;for(cin>>t;t;t--){int n;cin>>n;int yes=0,no=0;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){if(i==n){if(a[i]==a[1]){continue;}    if((a[i]+1)%3==a[1])yes++;elseno++;}else{if(a[i]==a[i+1]){continue;}    if((a[i]+1)%3==a[i+1])yes++;elseno++;}}if(yes>=no)cout<<"Yes"<<endl;elsecout<<"No"<<endl;}return 0;
}

力扣的一个题，让我想起了那个结论+完全背包才是正解的省赛题。这个题是结论+DFS做的

题意：给定n，统计从1-n中的所有特殊整数。
特殊整数：各个位置出现的数均不同

思路：假设n是9位数，那么显然从1位数到8位数都可以迅速计算出，因为这些位都是可以取满的，所以可以根据组合数学快速求出，到了第9位，那么直接搜索一下即可，复杂度很小，不是暴搜。

#include using namespace std;
char s[11];
int vis[11];
int len,ans;void DFS(int num,int pos)
{vis[num]=1;if(pos==len){ans++; return;}for(int i=0;i<=(num==(s[pos]-'0')?s[pos+1]-'0':9);i++){if(!vis[i]){DFS(i,pos+1);vis[i]=0;}}
}
int main()
{cin>>(s+1);len=strlen(s+1);for(int i=1;i<len;i++){int temp=9;for(int j=1;j<i;j++)temp*=(10-j);ans+=temp;}for(int i=1;i<=s[1]-'0';i++){DFS(i,1);vis[i]=0;}cout<<ans<<endl;return 0;
}

SG函数果然还是再开一篇文章吧

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！