2022.5.5-1

Ideas ： greedy , For reporting x For a rabbit , You can put x+1 Make a group of , There are deficiencies x+1 Make up for each one .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
int a[1005];
signed main()
{

int n;cin>>n;
for(int i=1;i<=n;i++)
{

int t;cin>>t;
a[t]++;
}
int ans=0;
for(int i=0;i<=1000;i++)
{

ans+=a[i];
if(a[i]%(i+1))
ans+=i+1-a[i]%(i+1);
}
cout<<ans<<endl;
}



2022.5.5-2

Ideas ： Stack matching , After each successful match, the bracket pair on the match will be removed , Then you can know the total length of all parentheses on the correct match of the current match through the subscript of the unmatched parentheses at the top of the stack .

#include<bits/stdc++.h>
#define int long long
#define MAXN 2000005
using namespace std;
int a[1005];
signed main()
{

string s;cin>>s;
stack<int> stk;
stk.push(-1);
int ans=0;
for(int i=0; i<s.size(); i++)
{

if(stk.size()>1&&s[i]==')'&&s[stk.top()]=='(')
{

stk.pop();
ans=max(ans,i-stk.top());
continue;
}
stk.push(i);
}
cout<<ans<<endl;
}



2022.5.5-3

Ideas ： You know, if you do on a bipartite graph dfs Every step will jump from the current set to another set , Therefore, the graph can be dyed according to the parity of the number of steps taken , If there is no conflict in coloring, it is a bipartite graph .

#include<bits/stdc++.h>
#define int long long
#define MAXN 505
using namespace std;
vector<int> edge[MAXN];
int col[MAXN];
int ans=1;
void dfs(int now,int p)
{

if(col[now]!=-1)
{

if(col[now]!=p)
ans=0;
return;
}
col[now]=p;
for(int i=0;i<edge[now].size();i++)
dfs(edge[now][i],1-p);
}
void solve()
{

ans=1;
memset(col,-1,sizeof(col));
for(int i=0;i<MAXN;i++)
edge[i].clear();
int n,m;cin>>n>>m;
for(int i=1;i<=m;i++)
{

int u,v;cin>>u>>v;
edge[u].push_back(v);
edge[v].push_back(u);
}
for(int i=1;i<=n;i++)
if(col[i]==-1)
dfs(i,0);
if(ans)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
signed main()
{

int T;cin>>T;
while(T--)
solve();
}



2022.5.6-1

Ideas ： Complete knapsack board

#include<bits/stdc++.h>
#define int long long
#define MAXN 200005
using namespace std;
int dp[MAXN];
int v[MAXN],c[MAXN];
signed main()
{

int n,x;cin>>n>>x;
for(int i=1;i<=n;i++)
cin>>v[i]>>c[i];
for(int i=1;i<=n;i++)
for(int j=v[i];j<=x;j++)
dp[j]=max(dp[j],dp[j-v[i]]+c[i]);
cout<<dp[x]<<endl;
}



2022.5.6-2

Ideas ：dfs Backtracking directly enumerates what numbers are filled in each grid , But you need to prune . After enumerating the numbers in one grid at a time , Check the nine palaces in the same row and belong to the same person to see if there is no conflict , It's legal to fill in , If it's illegal, go back . And if you find more than 1 When you create a scheme, you don't search and return directly , You can pass this question .

#include<bits/stdc++.h>
#define int long long
#define MAXN 200005
using namespace std;
int a[10][10];
int out[10][10];
int cnt=0;
bool check(int x,int y)
{

for(int i=1; i<=9; i++)
if(a[i][y]==a[x][y]&&i!=x
||a[x][i]==a[x][y]&&i!=y)
return false;
int bx=(x-1)/3*3+1,by=(y-1)/3*3+1;
for(int i=0; i<=2; i++)
for(int j=0; j<=2; j++)
if(a[bx+i][by+j]==a[x][y]&&((bx+i)!=x||(by+j)!=y))
return false;
return true;
}
void dfs(int x,int y)
{

if(cnt>1)return;
if(x==10)
{

if(y==9)
{

for(int i=1; i<=9; i++)
for(int j=1; j<=9; j++)
out[i][j]=a[i][j];
cnt++;
return;
}
x=1,y++;
}
if(a[x][y]&&check(x,y))
dfs(x+1,y);
else
{

for(int i=1; i<=9; i++)
{

a[x][y]=i;
if(check(x,y))
dfs(x+1,y);
}
a[x][y]=0;
}
}
signed main()
{

for(int i=1; i<=9; i++)
for(int j=1; j<=9; j++)
cin>>a[i][j];
dfs(1,1);
if(cnt!=1)cout<<"No Solution"<<endl;
else
{

for(int i=1; i<=9; i++)
{

for(int j=1; j<=9; j++)
cout<<out[i][j]<<' ';
cout<<endl;
}
}
}



2022.5.6-3

Ideas ： It can be seen that the sorting method according to bubble sorting is the one with the least number of exchanges , And each exchange makes the number of pairs in the array in reverse order -1, So find the reverse order pair , Here we use the merge sort method , There is also discretization + Tree array method , But the latter is not in the school recruitment program .

#include<bits/stdc++.h>
#define int long long
#define MAXN 200005
using namespace std;
int a[MAXN],b[MAXN];
int ans=0;
void merg(int l,int r)
{

if(l==r)return;
int mid=(l+r)/2;
merg(l,mid);
merg(mid+1,r);
int p1=l,p2=mid+1,p3=p1;
while(p1<=mid&&p2<=r)
{

if(a[p1]<=a[p2])
b[p3++]=a[p1++];
else
{

ans+=mid+1-p1;
b[p3++]=a[p2++];
}
}
while(p1<=mid) b[p3++]=a[p1++];
while(p2<=r) b[p3++]=a[p2++];
for(int i=l; i<=r; i++)a[i]=b[i];
}
signed main()
{

int n;cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
merg(1,n);
cout<<ans<<endl;
}



2022.5.7-1

Ideas ： Double pointer template question , Pay attention to how to write clearly .

#include<bits/stdc++.h>
#define int long long
#define MAXN 500005
using namespace std;
int a[MAXN];
signed main()
{

int s,n;cin>>s>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int ans=0x3f3f3f3f3f3f3f3f;
int L=1,sum=0;
for(int R=1;R<=n;R++)
{

sum+=a[R];
while(sum-a[L]>=s)
sum-=a[L++];
if(sum>=s)
ans=min(ans,R-L+1);
}
if(ans!=0x3f3f3f3f3f3f3f3f)
cout<<ans<<endl;
else cout<<0<<endl;
}



2022.5.7-2

Ideas ： The same number of Islands , Flooding algorithm .

#include<bits/stdc++.h>
#define int long long
#define MAXN 500005
using namespace std;
char mp[1005][1005];
void dfs(int x,int y)
{

if(mp[x][y]!='W')return;
mp[x][y]='.';
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++)
dfs(x+i,y+j);
}
signed main()
{

int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>mp[i][j];
int ans=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(mp[i][j]=='W')
{

ans++;
dfs(i,j);
}
cout<<ans<<endl;
}



2022.5.7-3

Ideas ：meet in middle,30 The number can be divided into two parts to enumerate whether to select , enumeration 2 15 2^{15} Next time , The enumeration method is used to compress the state .

#include<bits/stdc++.h>
#define int long long
#define MAXN 500005
using namespace std;
int a[35];
int getsum(int x,int b)
{

int ret=0;
for(int i=0;i<20;i++)
if((x>>i)&1)
ret+=a[i+b];
return ret;
}
int getmin(int a,int b)
{

for(int i=0;i<35;i++)
if(((a>>i)&1)!=((b>>i)&1))
return (a>>i)&1?a:b;
return a;
}
unordered_map<int,int> L;
signed main()
{

int n,m;cin>>n>>m;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
for(int i=0;i<(1<<(n/2));i++)
{

int now=getsum(i,0);
if(!L.count(now))L[now]=i;
else L[now]=getmin(L[now],i);
}
int ans=0;
for(int i=0;i<(1<<(n-n/2));i++)
{

int now=getsum(i,n/2);
if(now==m)ans=getmin(ans,(i<<n/2));
else if(L.count(m-now))
ans=getmin(ans,L[m-now]+(i<<n/2));
}
if(ans==0)
cout<<"No solution"<<endl;
else
for(int i=0;i<35;i++)
if((ans>>i)&1)
cout<<a[i]<<' ';
}



https://cdmana.com/2022/134/202205141349063771.html

Scroll to Top