2022 Niuke winter vacation algorithm basic training camp 3 personal problem solutions
Competition link: 2022 Niuke winter vacation algorithm basic training camp 3
A. Hello XXXX of zhinai
Main idea of the title:
Output "hello XXX"
Train of thought analysis:
Output "hello XXX"
AC Code:
print("hello world")
Question B wisdom is buying melons
Main idea of the title:
There are \ (n \) watermelons, weighing \ (w[i] \) respectively. You can buy one or half of them or not sell them. Ask the number of schemes when the total weight is \ (1,2,3....m \)
Train of thought analysis:
\(01 \) backpack, \ (dp[i][j] \) represents the number of schemes when the weight of the first \ (I \) watermelon is \ (j \)
Transfer equation: \ (dp[i][j]=dp[i-1][j-w_i]+dp[i-1][j-w_i/2]+dp[i-1][j] \)
AC Code:
#include<bits/stdc++.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define endl '\n'
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int mod=1e9+7;
const int maxn=1005;
int n,m;
int dp[maxn][maxn];
int a[maxn];
int main(){
IOS
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=0;i<=n;i++){
dp[i][0]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=dp[i-1][j];
if(j>=a[i])dp[i][j]=(dp[i][j]+dp[i-1][j-a[i]])%mod;
if(j>=a[i]/2)dp[i][j]=(dp[i][j]+dp[i-1][j-a[i]/2])%mod;
}
}
for(int i=1;i<=m;i++)cout<<dp[n][i]<<" ";
}
Question C: wisdom is another version
Main idea of the title:
Train of thought analysis:
AC Code:
The 01 string of question D zhinai is disturbed
Main idea of the title:
Give a \ (01 \) string and output a \ (01 \) string that is different from the original string but has the same number of \ (0 \) and \ (1 \)
Train of thought analysis:
Find the first "01" and change it to "10"
AC Code:
#include<bits/stdc++.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define endl '\n'
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn=1e6+5;
char s[maxn];
int main(){
IOS
int n;
cin>>n;
cin>>s;
for(int i=0;i<n-1;i++){
if(s[i]!=s[i+1]){
swap(s[i],s[i+1]);
break;
}
}
for(int i=0;i<n;i++){
cout<<s[i];
}
}
E. easy version
Main idea of the title:
There is a large integer with \ (n \) bits, and each bit has a color. You can exchange the adjacent bits of the same color, give a query \ (P, Q \) every time, and output the maximum value of this large integer after changing the bit of color \ (P \) to color \ (Q \)
Train of thought analysis:
Simulate the adjacent same color interval \ (sort() \) from large to small
AC Code:
#include<bits/stdc++.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define endl '\n'
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn=1e6+5;
const int mod=1e9+7;
int n,m,k;
int col[maxn];
char s[maxn];
bool cmp(char x,char y){
return x>y;
}
ll dfs(){
int l=1,r=1;
for(int i=2;i<=n;i++){
if(col[i]==col[i-1])r++;
else {
sort(s+l,s+r+1,cmp);
l=i;
r++;
}
}
sort(s+l,s+r+1,cmp);
ll ans=s[1]-'0';
for(int i=2;i<=n;i++){
ans=(ans*10+s[i]-'0')%mod;
}
return ans%mod;
}
int main(){
IOS
cin>>n>>m>>k;
cin>>s+1;
for(int i=1;i<=n;i++)cin>>col[i];
cout<<dfs()<<endl;
while(k--){
int x,y;
cin>>x>>y;
for(int i=1;i<=n;i++)if(col[i]==x)col[i]=y;
cout<<dfs()<<endl;
}
}
F. hard version
Main idea of the title:
Train of thought analysis:
AC Code:
G. easy version of the tree
Main idea of the title:
Give the parent-child relationship of a tree before and after rotation, and find the operation of restoration
Train of thought analysis:
We found that the simple version operation is less than or equal to \ (1 \), so we can only restore it once at most
When the two numbers as like as two peas are rotated, the obvious answer is (\ 0\).
Otherwise, we need to restore once, so we can find a node, and this node \ (x \) meets the following requirements:
After rotation, the parent node of \ (x \) is the child node of \ (x \) before rotation
AC Code:
#include<bits/stdc++.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define endl '\n'
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn=1e6+5;
struct node{
int x,y;
}a[maxn],b[maxn];
int fa[maxn],ba[maxn];
int main(){
IOS
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
fa[a[i].x]=i;
fa[a[i].y]=i;
}
int ok=1,pos=0;
for(int i=1;i<=n;i++){
cin>>b[i].x>>b[i].y;
ba[b[i].x]=i;
ba[b[i].y]=i;
if(b[i].x!=a[i].x||b[i].y!=a[i].y)ok=0;
}
if(ok)cout<<"0"<<endl;
else {
for(int i=1;i<=n;i++){
int x=i,y=ba[i];
if(fa[y]==x){
cout<<1<<endl;
cout<<x<<endl;
return 0;
}
}
}
}
H. hard version of the tree
Main idea of the title:
Train of thought analysis:
AC Code:
I. the password of question zhinai
Main idea of the title:
Give a string and find the number of substrings that meet the conditions
- Password is a string containing only upper and lower case English letters, numbers and special symbols
- The length of the password shall be no less than L characters and no more than R characters
- The password shall at least include three of the four types of characters: uppercase English letters, lowercase English letters, numbers and special symbols
Train of thought analysis:
For each position, take it as the beginning of the substring, and we can find the smallest interval that meets the conditions, and then we can calculate the number of qualified positions at each position and add it up
AC Code:
#include<bits/stdc++.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define endl '\n'
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn=1e6+5;
int n,l,r;
char s[maxn];
int sum[maxn][5];
bool ck(int x,int y){
int tot=0;
for(int i=1;i<=4;i++){
if(sum[y][i]-sum[x-1][i]==0)tot++;
}
if(tot>1)return false;
return true;
}
int main(){
IOS
cin>>n>>l>>r;
cin>>s+1;
for(int i=1;i<=n;i++){
for(int j=1;j<=4;j++)sum[i][j]=sum[i-1][j];
if(s[i]>='a'&&s[i]<='z')sum[i][1]++;
else if(s[i]>='A'&&s[i]<='Z')sum[i][2]++;
else if(s[i]>='0'&&s[i]<='9')sum[i][3]++;
else sum[i][4]++;
}
ll ans=0;
for(int i=1;i<=n-l+1;i++){
int ll=i+l-1,rr=min(i+r-1,n);
int pos=-1;
while (ll<= rr){
int mid = ll + rr >> 1;
if (ck(i,mid))
rr = mid-1,pos=mid;
else
ll = mid + 1;
}
if(pos!=-1)ans+=min(i+r-1,n)-pos+1;
}
cout<<ans<<endl;
}
C language modular division equation of J problem zhinai
Main idea of the title:
Train of thought analysis:
AC Code:
Another version of C language modular division equation of K problem zhinai
Main idea of the title:
Train of thought analysis:
AC Code:
The database of L Ti Zhi Nai
Main idea of the title:
Give a table of \ (n*m \) in the database. After grouping according to \ (group by \), how many data are there in each new table
Train of thought analysis:
Set the data in the non group to \ (0 \), and then enumerate and judge
Comparison \ (vector \) or \ (hash \) can be used for judgment
AC Code:
#include<bits/stdc++.h>
#include <cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define endl '\n'
#define pii pair<int,int>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int maxn=1005;
int n,m;
vector<int>a[maxn];
map<string ,int>mp;
vector<int>q;
int vis[maxn];
int st[maxn];
stack<int>stk;
int main(){
//IOS
cin>>n>>m;
for(int i=1;i<=m;i++){
string op;
cin>>op;
mp[op]=i;
}
a->resize(n+1);
for(int i=0;i<=n;i++)a[i].resize(m+1);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
getchar();
string s;
getline(cin,s);
for(int i=0;i<s.size();i++){
if(s[i]=='Y'){
string now;
int pos=i+2;
while(s[pos]!=';'){
if(s[pos]==','){
q.push_back(mp[now]);
now="";
pos++;
continue;
}
now+=s[pos];
pos++;
}
q.push_back(mp[now]);
break;
}
}
for(int i=0;i<q.size();i++){
vis[q[i]]=1;
}
for(int j=1;j<=m;j++){
if(vis[j]==0)for(int i=1;i<=n;i++){
a[i][j]=0;
}
}
for(int i=1;i<=n;i++){
if(st[i])continue;
int now=1;
for(int j=i+1;j<=n;j++){
if(a[i]==a[j]){
now++;
st[j]=1;
}
}
stk.push(now);
}
cout<<stk.size()<<endl;
while(stk.size()){
cout<<stk.top()<<" ";
stk.pop();
}
}