差不多2个小时才AK,题目难度还行吧。

自己好菜。

题目地址：/test/16516564/summary

目录

万万没想到之聪明的编辑 【模拟】万万没想到之抓捕孔连顺【思维 / 二分】雀魂启动！【枚举 / 二进制枚举】特征提取【模拟 / 哈希表】毕业旅行问题【状压DP】找零【贪心】机器人跳跃问题【二分】

万万没想到之聪明的编辑 【模拟】

我们将连续相同的字符，压缩成一个pair<char,int>类型，只存字符和个数，考虑到3个以上的相同字符会最多存俩，故存的时候直接存俩个。

#include<bits/stdc++.h>using namespace std;int main(void){int n; cin>>n;while(n--){string s; cin>>s;vector< pair<char,int> >ve; for(int i=0;i<s.size();i++){int j=i,cnt=1;while(j+1<s.size()&&s[i]==s[j+1]) j++,cnt++;ve.push_back({s[i],min(cnt,2)});//压缩，最多只存俩i=j;}string ans;for(int i=0;i<ve[0].second;i++) ans+=ve[0].first;for(int i=1;i<ve.size();i++){if(ve[i].second>=2&&ve[i-1].second>=2) ve[i].second--;//2,2这种情况for(int j=0;j<ve[i].second;j++) ans+=ve[i].first;}cout<<ans<<endl;}return 0;}

万万没想到之抓捕孔连顺【思维 / 二分】

#include<bits/stdc++.h>using namespace std;const int N=1e6+10;const int mod=99997867;typedef long long int LL;LL a[N],n,r;int main(void){cin>>n>>r;for(int i=0;i<n;i++) cin>>a[i];LL ans=0;for(int i=0;i<n;i++){LL temp=a[i]+r;LL len=lower_bound(a+i,a+n,temp)-a;//找到最远的满足的点if(a[len]>temp) len--;len=min(len,n-1);if(len-i>1){LL t=len-i;//有t个可以选择ans=(ans+t*(t-1)/2)%mod;//t个里面选2}}cout<<ans%mod;return 0;}

雀魂启动！【枚举 / 二进制枚举】

最恶心的一道题，题目没说明顺子和刻子总和是4个，我一直以为是4个刻子或4个顺子。

后来才直到是顺子和刻子的总和是4个就行。

#include<bits/stdc++.h>using namespace std;int a[15],cnt[15],backup[15];set<int>st,s;bool check1(int i){if(backup[i]>=3) {backup[i]-=3;return true;}return false;}bool check2(int i){if(backup[i]&&backup[i+1]&&backup[i+2]){backup[i]--,backup[i+1]--,backup[i+2]--;return true;}return false;}bool check(int x){for(int i=0;i<16;i++)//二进制枚举顺子和刻子各位多少，且出现的顺序{memcpy(backup,cnt,sizeof cnt);backup[x]-=2;if(backup[x]<0) return false;int k=0;for(int j=1;j<=9;){int flag=0;if((i>>k)&1) {if(check1(j)) k++,flag=1;}else {if(check2(j)) k++,flag=1;}if(!flag) j++;if(k==4) return true;}}return false;}int main(void){for(int i=0;i<13;i++) cin>>a[i],cnt[a[i]]++,s.insert(a[i]);vector<int>ans;for(int i=1;i<=9;i++) if(cnt[i]<=3) st.insert(i);for(auto i=st.begin();i!=st.end();i++)//枚举抽哪张{cnt[*i]++;bool flag=0;for(auto j=s.begin();j!=s.end();j++)//枚举哪个是雀头{int t=*j;if(check(t)) flag=1;}if(flag) ans.push_back(*i);cnt[*i]--;}for(int i=0;i<ans.size();i++) {if(i) cout<<" ";cout<<ans[i];}if(!ans.size()) cout<<0;return 0;}

特征提取【模拟 / 哈希表】

#include<bits/stdc++.h>using namespace std;int t,n,m;int main(void){cin>>t;while(t--){cin>>n;int ans=1;map<pair<int,int>,int>mp;for(int i=0;i<n;i++){cin>>m;map<pair<int,int>,int>st;set<pair<int,int>>s;for(int j=0;j<m;j++){int x,y; scanf("%d%d",&x,&y);st[{x,y}]++;s.insert({x,y});}for(auto j=mp.begin();j!=mp.end();j++){auto temp=j->first;if(st[temp]==0) mp[temp]=0;//说明不连续了}for(auto j=s.begin();j!=s.end();j++){auto temp=*j;mp[temp]++;ans=max(ans,mp[temp]);}}cout<<ans<<endl;}return 0;}

毕业旅行问题【状压DP】

经典的状压DP，TSP问题。

不过这里数据范围弱，开18过的。按道理说得开20，但是开20就超过了本题的要求的内存。

一时间没想到好的优化空间的方法。

#include<bits/stdc++.h>using namespace std;const int N=18;int f[1<<N][N],w[N][N],n;//f[i][j] 表示走了i的状态 最终点是j的花费int main(void){cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>w[i][j];memset(f,0x3f,sizeof f);f[1][0]=0;for(int i=0;i<(1<<n);i++){for(int j=0;j<n;j++){if(i>>j&1){for(int k=0;k<n;k++){int temp=i-(1<<j);if(temp>>k&1) f[i][j]=min(f[i][j],f[temp][k]+w[k][j]);}}}}int ans=1e9;for(int i=1;i<n;i++) ans=min(ans,f[(1<<n)-1][i]+w[i][0]);//枚举最终的点，加上回家的花费cout<<ans;return 0;}

找零【贪心】

简单的贪心

#include<bits/stdc++.h>using namespace std;int a[4]={64,16,4,1};int main(void){int n; cin>>n;n=1024-n;int cnt=0;for(int i=0;i<4;i++){int t=n/a[i];n-=a[i]*t;cnt+=t;}cout<<cnt;return 0;}

机器人跳跃问题【二分】

洛谷的原题

#include<bits/stdc++.h>using namespace std;const int N=1e6+10;typedef long long int LL;LL h[N],n;bool check(LL x){for(int i=0;i<n;i++){x=2*x-h[i];if(x>1e9) return true;if(x<0) return false;}return true;}int main(void){cin>>n;for(int i=0;i<n;i++) cin>>h[i];LL l=0,r=1e9;while(l<r){LL mid=l+r>>1;if(check(mid)) r=mid;else l=mid+1;}cout<<l<<endl;return 0;}