<> Byte runout 2019 Spring trick algorithm problem
<>1. summary
difficulty ： Easy to medium .
Some questions are too bad , No data range , And there is a problem with the memory setting , If it is a brush question, it is not recommended to brush it .
<>2. subject
<>(1)
Simple string emulation .
#include<bits/stdc++.h> using namespace std; int main(){ int n; scanf("%d",&n);
for(int i=1;i<=n;i++){ string s;cin>>s; int p = 0; int ok = 0; do{ int m = s.
size(); ok = 0; for(int j=0;j<m;j++){ if(j+2<m && s[j+1] == s[j] && s[j+2] == s[
j]){ s.erase(s.begin()+j); ok = 1;break; } if(j+3<m && s[j+1] == s[j] && s[j+2]
== s[j+3]){ s.erase(s.begin()+j+3); ok = 1; break; } } }while(ok); cout<<s<<'\n'
; } return 0; }
<>(2)
Simple counting problem .
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef
unsigned long long ull; const int N=1e6+5,M=2e4+5,inf=0x3f3f3f3f,mod=99997867;
const int hashmod[4] = {402653189,805306457,1610612741,998244353}; #define
mst(a,b) memset(a,b,sizeof a) #define db double #define PII pair<int,int> #
define PLL pair<ll,ll> #define x first #define y second #define pb emplace_back
#define SZ(a) (int)a.size() #define rep(i,a,b) for(int i=a;i<=b;++i) #define
per(i,a,b) for(int i=a;i>=b;--i) #define IOS
ios::sync_with_stdio(false),cin.tie(nullptr) void Print(int *a,int n){ for(int i
=1;i<n;i++) printf("%d ",a[i]); printf("%d\n",a[n]); } template <typename T>
//x=max(x,y) x=min(x,y) void cmx(T &x,T y){ if(x<y) x=y; } template <typename T>
void cmn(T &x,T y){ if(x>y) x=y; } int n,d; int a[N]; int main(){ scanf("%d%d",&
n,&d); rep(i,1,n){ scanf("%d",&a[i]); } ll s = 0; rep(i,1,n){ int p =
upper_bound(a+i,a+n+1,a[i]+d)-a-1; ll tmp = p-i; ll v = max(tmp*(tmp-1)>>1,0ll);
//printf("i=%d,v=%lld\n",i,v); s = (s+v)%mod; } printf("%lld\n",s); return 0; }
<>(3)
dfs It's over .
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef
unsigned long long ull; const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const int hashmod[4] = {402653189,805306457,1610612741,998244353}; #define
mst(a,b) memset(a,b,sizeof a) #define db double #define PII pair<int,int> #
define PLL pair<ll,ll> #define x first #define y second #define pb emplace_back
#define SZ(a) (int)a.size() #define rep(i,a,b) for(int i=a;i<=b;++i) #define
per(i,a,b) for(int i=a;i>=b;--i) #define IOS
ios::sync_with_stdio(false),cin.tie(nullptr) void Print(int *a,int n){ for(int i
=1;i<n;i++) printf("%d ",a[i]); printf("%d\n",a[n]); } template <typename T>
//x=max(x,y) x=min(x,y) void cmx(T &x,T y){ if(x<y) x=y; } template <typename T>
void cmn(T &x,T y){ if(x>y) x=y; } int a[10]; int b[10]; int c[10],ok; void dfs(
int x){ if(ok) return; if(x==4){ ok = 1; return; } for(int i=1;i<10;i++){ if(a[i
]>=3){ a[i]-=3; dfs(x+1); a[i]+=3; } } for(int i=1;i<=7;i++){ if(a[i]>0 && a[i+1
]>0 &&a[i+2]>0){ a[i]--,a[i+1]--,a[i+2]--; dfs(x+1); a[i]++,a[i+1]++,a[i+2]++; }
} } bool ck(){ for(int i=1;i<=9;i++){ if(a[i]<2) continue; a[i]-=2; ok = 0; dfs(
0); a[i]+=2; if(ok) return true; } return false; } int main(){ rep(i,1,9) b[i] =
4; rep(i,1,13){ int x;scanf("%d",&x); a[x]++; b[x]--; } int jg =0; for(int i=1;i
<=9;i++){ if(!b[i]) continue; a[i]++; if(ck()) printf("%d ",i),jg=1; a[i]--; }
if(!jg) puts("0"); return 0; }
<>(4)
Simple simulation problem .
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef
unsigned long long ull; const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const int hashmod[4] = {402653189,805306457,1610612741,998244353}; #define
mst(a,b) memset(a,b,sizeof a) #define db double #define PII pair<int,int> #
define PLL pair<ll,ll> #define x first #define y second #define pb emplace_back
#define SZ(a) (int)a.size() #define rep(i,a,b) for(int i=a;i<=b;++i) #define
per(i,a,b) for(int i=a;i>=b;--i) #define IOS
ios::sync_with_stdio(false),cin.tie(nullptr) void Print(int *a,int n){ for(int i
=1;i<n;i++) printf("%d ",a[i]); printf("%d\n",a[n]); } template <typename T>
//x=max(x,y) x=min(x,y) void cmx(T &x,T y){ if(x<y) x=y; } template <typename T>
void cmn(T &x,T y){ if(x>y) x=y; } map<PII,vector<int> >mp; int main(){ int t;
cin>>t; while(t--){ mp.clear(); int n;cin>>n; rep(i,1,n){ int m ;cin>>m; map<PII
,bool>vis; rep(j,1,m){ int x,y;cin>>x>>y; if(!vis[{x,y}]) mp[{x,y}].pb(i),vis[{x
,y}] =true; } } int mx = 0; int ans = 0; for(auto [_,v]:mp){ int sz= SZ(v); int
cnt= 0; for(int i=0;i<sz;i++){ if(!i ||v[i]==v[i-1]+1){ cnt++; } else { ans=max(
ans,cnt); cnt = 1; } } ans=max(ans,cnt); } printf("%d\n",ans); } return 0; }
<>(5)
Compare the shape pressure of the plate dp, But what happened , Card space .
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef
unsigned long long ull; const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const int hashmod[4] = {402653189,805306457,1610612741,998244353}; #define
mst(a,b) memset(a,b,sizeof a) #define db double #define PII pair<int,int> #
define PLL pair<ll,ll> #define x first #define y second #define pb emplace_back
#define SZ(a) (int)a.size() #define rep(i,a,b) for(int i=a;i<=b;++i) #define
per(i,a,b) for(int i=a;i>=b;--i) #define IOS
ios::sync_with_stdio(false),cin.tie(nullptr) void Print(int *a,int n){ for(int i
=1;i<n;i++) printf("%d ",a[i]); printf("%d\n",a[n]); } template <typename T>
//x=max(x,y) x=min(x,y) void cmx(T &x,T y){ if(x<y) x=y; } template <typename T>
void cmn(T &x,T y){ if(x>y) x=y; } int a[20][20]; int dp[1<<18][18]; int main(){
int n ;cin>>n; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>a[i][j]; int st =
1<<n; mst(dp,0x3f); dp[1][0] = 0; int ans = 1e9; for(int i=0;i<st;i++) for(int j
=0;j<n;j++){ if(i>>j&1){ for(int k=0;k<n;k++){ if(!(i>>k&1)){ cmn(dp[i|(1<<k)][k
],dp[i][j]+a[j][k]); } } } } st--; for(int i=0;i<n;i++) cmn(ans,dp[st][i]+a[i][0
]); printf("%d\n",ans); return 0; }
<>(6)
The greedy question in the classic .
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef
unsigned long long ull; const int N=1e3+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const int hashmod[4] = {402653189,805306457,1610612741,998244353}; #define
mst(a,b) memset(a,b,sizeof a) #define db double #define PII pair<int,int> #
define PLL pair<ll,ll> #define x first #define y second #define pb emplace_back
#define SZ(a) (int)a.size() #define rep(i,a,b) for(int i=a;i<=b;++i) #define
per(i,a,b) for(int i=a;i>=b;--i) #define IOS
ios::sync_with_stdio(false),cin.tie(nullptr) void Print(int *a,int n){ for(int i
=1;i<n;i++) printf("%d ",a[i]); printf("%d\n",a[n]); } template <typename T>
//x=max(x,y) x=min(x,y) void cmx(T &x,T y){ if(x<y) x=y; } template <typename T>
void cmn(T &x,T y){ if(x>y) x=y; } int main(){ int n;cin>>n; n = 1024-n; int s =
0; s+=n/64; n%=64; s+=n/16; n%=16; s+=n/4; n%=4; s+=n; printf("%d\n",s); return
0; }
<>(7)
Just two points , Because it's a recursive question , Actually, it's OK O(n) Backward recurrence .
Pay attention to two points check Implosion range .
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef
unsigned long long ull; const int N=2e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
const int hashmod[4] = {402653189,805306457,1610612741,998244353}; #define
mst(a,b) memset(a,b,sizeof a) #define db double #define PII pair<int,int> #
define PLL pair<ll,ll> #define x first #define y second #define pb emplace_back
#define SZ(a) (int)a.size() #define rep(i,a,b) for(int i=a;i<=b;++i) #define
per(i,a,b) for(int i=a;i>=b;--i) #define IOS
ios::sync_with_stdio(false),cin.tie(nullptr) void Print(int *a,int n){ for(int i
=1;i<n;i++) printf("%d ",a[i]); printf("%d\n",a[n]); } template <typename T>
//x=max(x,y) x=min(x,y) void cmx(T &x,T y){ if(x<y) x=y; } template <typename T>
void cmn(T &x,T y){ if(x>y) x=y; } ll a[N],n; bool ck(ll x){ ll e = x; rep(i,1,n
){ ll v = e - a[i]; //if(x==4) printf("e=%lld,v=%lld\n",e,v); e+=v; if(e<0)
return false; if(e>1e5) return true; } // /printf("x=%lld\n",x); return true; }
int main(){ cin>>n; rep(i,1,n) cin>>a[i]; ll l=1,r=1e5;ll ans = 0; while(l<=r){
ll m= l+r>>1; //printf("m=%d\n",m); if(ck(m)) ans=m,r=m-1; else l=m+1; } printf(
"%lld\n",ans); return 0; }
Technology