catalogue
G-air conditioner remote control
A - Digital Games
Title:
Train of thought analysis:
What a metaphysical problem! (it turns out that I'm blind. I need to use fast reading and cout. Don't be careful!
Then calculate the analog operation of bit operation
The last one is negative, just ^
Then count the number of 1. You can use lowbit to operate. The function of lowbit is to take the last 1 under the binary and all the subsequent 0
While counting, you can find the first bit 1, which is convenient for even operation
Code implementation:
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/*
* __----~~~~~~~~~~~------___
* . . ~~//====...... __--~ ~~
* -. \_|// |||\\ ~~~~~~::::... /~
* ___-==_ _-~o~ \/ ||| \\ _/~~-
* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~
* _-~~ .=~ | \\-_ '-~7 /- / || \ /
* .~ .~ | \\ -_ / /- / || \ /
* / ____ / | \\ ~-_/ /|- _/ .|| \ /
* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\
* ' ~-| /| |-~\~~ __--~~
* |-~~-_/ | | ~\_ _-~ /\
* / \ \__ \/~ \__
* _--~ _/ | .-~~____--~-/ ~~==.
* ((->/~ '.|||' -_| ~~-/ , . _||
* -_ ~\ ~~---l__i__i__i--~~_/
* _-~-__ ~) \--______________--~~
* //.-~~~-~_--~- |-------~~~~~~~~
* //.-~~~--\
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* God beast bless never BUG
*/
int lowbit(int x){
return x&-x;
}
int x,n;
int main(){
scanf("%d",&n);
while (n--) {
scanf("%d",&x);
int ans=0;
while (x) {
int a1=x;
int num=0;
int a2=0;
while (a1) {
if(a1==lowbit(a1)) a2=lowbit(a1);
num++;
a1-=lowbit(a1);
}
if(num&1) {
x^=1;
}
else{
x-=a2;
}
ans++;
}
printf("%d\n", ans);
}
}
B-jump jump jump
Title:
Train of thought analysis:
A topic of interval DP:
The state transition equation is: f[l][r]=max(dp(l+1,r)+len*a[l],dp(l,r-1)+len*a[r]);
len is the interval length, which is realized by memorizing
Then enumerate the starting point and calculate the maximum value
Code implementation:
const int MAX=4010;
int n;
int a[MAX];
ll f[MAX][MAX];
int dp(int l,int r){
if(f[l][r]) return f[l][r];
if(l==r) return a[l];
int len=r-l+1;
return f[l][r]=max(dp(l+1,r)+len*a[l],dp(l,r-1)+len*a[r]);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];
}
ll ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,dp(i,i+n-1));
}
cout<<ans;
}
C-number matching
Title:
Train of thought analysis:
It uses the idea similar to hash
If i and j have coincidence bits > = k, there must be coincidence of k bits
We enumerate each k-bit number of i and put it into the bucket
Then enumerate every k digits of j and look it up in the bucket
If found++
Code implementation:
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/*
* __----~~~~~~~~~~~------___
* . . ~~//====...... __--~ ~~
* -. \_|// |||\\ ~~~~~~::::... /~
* ___-==_ _-~o~ \/ ||| \\ _/~~-
* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~
* _-~~ .=~ | \\-_ '-~7 /- / || \ /
* .~ .~ | \\ -_ / /- / || \ /
* / ____ / | \\ ~-_/ /|- _/ .|| \ /
* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\
* ' ~-| /| |-~\~~ __--~~
* |-~~-_/ | | ~\_ _-~ /\
* / \ \__ \/~ \__
* _--~ _/ | .-~~____--~-/ ~~==.
* ((->/~ '.|||' -_| ~~-/ , . _||
* -_ ~\ ~~---l__i__i__i--~~_/
* _-~-__ ~) \--______________--~~
* //.-~~~-~_--~- |-------~~~~~~~~
* //.-~~~--\
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* God beast bless never BUG
*/
int n,k;
const int MAX=114514;
int Hash[MAX];
int ans;
int a[MAX];
void insert(int x){
int pos=0;
while (x) {
a[++pos]=x&1;
x>>=1;
}
int s=0;
for(int i=1;i<=k;i++){
s=s*2+a[i];
}
Hash[s]=1;
for(int i=k+1;i<=pos;i++){
// s=2*(s-a[i-k]*(1ll<<(k-1)))+a[i];
s=2*(s-(1ll<<(k-1))*a[i-k])+a[i];
Hash[s]=1;
}
}
void query(int x){
int pos=0;
while (x) {
a[++pos]=x&1;
x>>=1;
}
int s=0;
for(int i=1;i<=k;i++){
s=s*2+a[i];
}
if(Hash[s]){
ans++;
return;
}
for(int i=k+1;i<=pos;i++){
s=2*(s-(1ll<<(k-1))*a[i-k])+a[i];
if(Hash[s]){
ans++;
return;
}
}
}
void clear(int x) {
int pos=0;
while (x) {
a[++pos]=x&1;
x>>=1;
}
int s=0;
for(int i=1;i<=k;i++){
s=s*2+a[i];
}
Hash[s]=0;
for(int i =k+1;i<=pos;i++) {
s=2*(s-(1ll<<(k-1))*a[i-k])+a[i];
Hash[s] = 0;
}
// mms(Hash,0);
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
int ws1 = log2(i) + 1, ws2 = log2(j) + 1;
if(ws1 < k || ws2 < k) {
continue;
}
insert(i);
query(j);
clear(i);
}
}
cout<<ans;
}
D-graceful string
Title:
Train of thought analysis:
Is to find the number of adjacent different intervals
Code implementation:
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/*
* __----~~~~~~~~~~~------___
* . . ~~//====...... __--~ ~~
* -. \_|// |||\\ ~~~~~~::::... /~
* ___-==_ _-~o~ \/ ||| \\ _/~~-
* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~
* _-~~ .=~ | \\-_ '-~7 /- / || \ /
* .~ .~ | \\ -_ / /- / || \ /
* / ____ / | \\ ~-_/ /|- _/ .|| \ /
* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\
* ' ~-| /| |-~\~~ __--~~
* |-~~-_/ | | ~\_ _-~ /\
* / \ \__ \/~ \__
* _--~ _/ | .-~~____--~-/ ~~==.
* ((->/~ '.|||' -_| ~~-/ , . _||
* -_ ~\ ~~---l__i__i__i--~~_/
* _-~-__ ~) \--______________--~~
* //.-~~~-~_--~- |-------~~~~~~~~
* //.-~~~--\
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* God beast bless never BUG
*/
const int MAX=10001;
int w(string s){
int ans=0;
for(int i=0;i<s.length()-1;i++){
if(s[i]==s[i+1]){
ans++;
}
}
return ans;
}
int main(){
int n;
cin>>n;
while (n--) {
string s;
cin>>s;
cout<<s.length()+w(s)<<endl;
}
}
E-grouping
Title:
Train of thought analysis:
The biggest and the smallest are easy to think of two points
But the subject data is very small
You can also enumerate check directly
Code implementation:
Code 1:
const int MAX=100010;
int n,m;
int a[MAX];
map<int,int>mp;
vector<int>v;
int ch(int x){
int ans=0;
for(int i=0;i<v.size();i++){
double y=x;
ans+=ceil(mp[v[i]]/y);
}
// cout<<"ans= "<<ans<<endl;
if(ans>m) return 0;
return 1;
}
int main(){
cin>>n>>m;
set<int>st;
for(int i=1;i<=n;i++){
cin>>a[i];
if(st.count(a[i])==0){
st.insert(a[i]);
v.push_back(a[i]);
}
mp[a[i]]++;
}
// cout<<mp[2]<<endl;
// cout<<mp[3]<<endl;
if(st.size()>m){
cout<<-1;
return 0;
}
for(int i=1;i<=n;i++){
if(ch(i)){
cout<<i;
return 0;
}
}
cout<<-1;
}
Code 2 (two points)
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/*
* __----~~~~~~~~~~~------___
* . . ~~//====...... __--~ ~~
* -. \_|// |||\\ ~~~~~~::::... /~
* ___-==_ _-~o~ \/ ||| \\ _/~~-
* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~
* _-~~ .=~ | \\-_ '-~7 /- / || \ /
* .~ .~ | \\ -_ / /- / || \ /
* / ____ / | \\ ~-_/ /|- _/ .|| \ /
* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\
* ' ~-| /| |-~\~~ __--~~
* |-~~-_/ | | ~\_ _-~ /\
* / \ \__ \/~ \__
* _--~ _/ | .-~~____--~-/ ~~==.
* ((->/~ '.|||' -_| ~~-/ , . _||
* -_ ~\ ~~---l__i__i__i--~~_/
* _-~-__ ~) \--______________--~~
* //.-~~~-~_--~- |-------~~~~~~~~
* //.-~~~--\
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* God beast bless never BUG
*/
const int MAX=100010;
int n,m;
int a[MAX];
int ch(int x){
int ans=0;
for(int i=1;i<=MAX;i++){
if(a[i]){
ans+=(a[i]-1)/x+1;
}
}
return ans<=m;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
int x;
cin>>x;
a[x]++;
}
int l=1;
int r=n;
while (l+1<r) {
int mid=(l+r)>>1;
if(ch(mid)){
r=mid;
}
else l=mid;
}
if(!ch(r)) r=-1;
cout<<r;
}
F - bridge crossing
Title:
Train of thought analysis:
This problem can be understood as dp model or shortest path model
Code implementation:
Code 1dp
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/*
* __----~~~~~~~~~~~------___
* . . ~~//====...... __--~ ~~
* -. \_|// |||\\ ~~~~~~::::... /~
* ___-==_ _-~o~ \/ ||| \\ _/~~-
* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~
* _-~~ .=~ | \\-_ '-~7 /- / || \ /
* .~ .~ | \\ -_ / /- / || \ /
* / ____ / | \\ ~-_/ /|- _/ .|| \ /
* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\
* ' ~-| /| |-~\~~ __--~~
* |-~~-_/ | | ~\_ _-~ /\
* / \ \__ \/~ \__
* _--~ _/ | .-~~____--~-/ ~~==.
* ((->/~ '.|||' -_| ~~-/ , . _||
* -_ ~\ ~~---l__i__i__i--~~_/
* _-~-__ ~) \--______________--~~
* //.-~~~-~_--~- |-------~~~~~~~~
* //.-~~~--\
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* God beast bless never BUG
*/
const int MAX=100001;
int n,m;
int a[MAX];
int dp[MAX];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
mms(dp,INF);
dp[1]=0;
for(int i=1;i<=n;i++){
if(a[i]>0){
for(int j=i+1;j<=a[i]+i;j++){
dp[j]=min(dp[j],dp[i]+1);
}
}
else{
for(int j=i+a[i];j<=i-1;j++){
dp[j]=min(dp[j],dp[i]+1);
}
}
}
if(dp[n]>=INF) cout<<-1;
else cout<<dp[n];
}
Code 2 shortest
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/*
* __----~~~~~~~~~~~------___
* . . ~~//====...... __--~ ~~
* -. \_|// |||\\ ~~~~~~::::... /~
* ___-==_ _-~o~ \/ ||| \\ _/~~-
* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~
* _-~~ .=~ | \\-_ '-~7 /- / || \ /
* .~ .~ | \\ -_ / /- / || \ /
* / ____ / | \\ ~-_/ /|- _/ .|| \ /
* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\
* ' ~-| /| |-~\~~ __--~~
* |-~~-_/ | | ~\_ _-~ /\
* / \ \__ \/~ \__
* _--~ _/ | .-~~____--~-/ ~~==.
* ((->/~ '.|||' -_| ~~-/ , . _||
* -_ ~\ ~~---l__i__i__i--~~_/
* _-~-__ ~) \--______________--~~
* //.-~~~-~_--~- |-------~~~~~~~~
* //.-~~~--\
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* God beast bless never BUG
*/
#define N 2005
using namespace std;
struct edge {
int v, nxt;
} e[N * N << 1];
int p[N], eid;
void init() {
memset(p, -1, sizeof p);
eid = 0;
}
void insert(int u, int v) {
e[eid].v = v;
e[eid].nxt = p[u];
p[u] = eid ++;
}
int dis[N], n, a[N];
queue<int> q;
void bfs(int S) {
memset(dis, -1, sizeof dis);
dis[S] = 0; q.push(S);
while(q.size()) {
int u = q.front(); q.pop();
for(int i = p[u]; i + 1; i = e[i].nxt) {
int v = e[i].v;
if(dis[v] == -1) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
}
int main() {
init();
scanf("%d", &n);
for(int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
if(a[i] > 0) {
for(int j = i + 1; j <= min(n, a[i] + i); j ++) {
insert(j, i);
}
}
if(a[i] < 0) {
for(int j = 1; j <= max(1, i + a[i]); j ++) {
insert(j, i);
}
}
}
bfs(n);
printf("%d", dis[1]);
return 0;
}
G-air conditioner remote control
Title:
Train of thought analysis:
The data range is relatively small. We can directly enumerate k, preprocess the prefix and find the maximum value
Or solve it with the idea of difference
Code implementation:
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/*
* __----~~~~~~~~~~~------___
* . . ~~//====...... __--~ ~~
* -. \_|// |||\\ ~~~~~~::::... /~
* ___-==_ _-~o~ \/ ||| \\ _/~~-
* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~
* _-~~ .=~ | \\-_ '-~7 /- / || \ /
* .~ .~ | \\ -_ / /- / || \ /
* / ____ / | \\ ~-_/ /|- _/ .|| \ /
* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\
* ' ~-| /| |-~\~~ __--~~
* |-~~-_/ | | ~\_ _-~ /\
* / \ \__ \/~ \__
* _--~ _/ | .-~~____--~-/ ~~==.
* ((->/~ '.|||' -_| ~~-/ , . _||
* -_ ~\ ~~---l__i__i__i--~~_/
* _-~-__ ~) \--______________--~~
* //.-~~~-~_--~- |-------~~~~~~~~
* //.-~~~--\
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* God beast bless never BUG
*/
const int MAX=1000000;
int a[MAX+10];
int n,p;
int main(){
n=read();
p=read();
for(int i=1;i<=n;i++){
int x;
x=read();
a[x]++;
}
for(int i=1;i<=MAX;i++){
a[i]+=a[i-1];
}
int ans=0;
for(int i=1;i<=MAX;i++){
ans=max(ans,a[min(MAX,p+i)]-a[max(0,i-p-1)]);
}
cout<<ans;
}
Code 2
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/*
* __----~~~~~~~~~~~------___
* . . ~~//====...... __--~ ~~
* -. \_|// |||\\ ~~~~~~::::... /~
* ___-==_ _-~o~ \/ ||| \\ _/~~-
* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~
* _-~~ .=~ | \\-_ '-~7 /- / || \ /
* .~ .~ | \\ -_ / /- / || \ /
* / ____ / | \\ ~-_/ /|- _/ .|| \ /
* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\
* ' ~-| /| |-~\~~ __--~~
* |-~~-_/ | | ~\_ _-~ /\
* / \ \__ \/~ \__
* _--~ _/ | .-~~____--~-/ ~~==.
* ((->/~ '.|||' -_| ~~-/ , . _||
* -_ ~\ ~~---l__i__i__i--~~_/
* _-~-__ ~) \--______________--~~
* //.-~~~-~_--~- |-------~~~~~~~~
* //.-~~~--\
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* God beast bless never BUG
*/
const int MAX=2000210;
int n,p;
int a[MAX];
int main(){
cin>>n>>p;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
a[max(1,x-p)]++;
a[x+p+1]--;
}
int ans=0;
int now=0;
for(int i=1;i<=MAX;i++){
now+=a[i];
ans=max(ans,now);
}
cout<<ans<<endl;
}
I-gymnastics formation
Title:
Train of thought analysis:
The data is very small. We can directly enumerate all States (Full Permutation, n! Complexity)
Then check
Idea 2. State compression dp
Train of thought 3. Violent search
Code implementation:
Enumeration:
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/*
* __----~~~~~~~~~~~------___
* . . ~~//====...... __--~ ~~
* -. \_|// |||\\ ~~~~~~::::... /~
* ___-==_ _-~o~ \/ ||| \\ _/~~-
* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~
* _-~~ .=~ | \\-_ '-~7 /- / || \ /
* .~ .~ | \\ -_ / /- / || \ /
* / ____ / | \\ ~-_/ /|- _/ .|| \ /
* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\
* ' ~-| /| |-~\~~ __--~~
* |-~~-_/ | | ~\_ _-~ /\
* / \ \__ \/~ \__
* _--~ _/ | .-~~____--~-/ ~~==.
* ((->/~ '.|||' -_| ~~-/ , . _||
* -_ ~\ ~~---l__i__i__i--~~_/
* _-~-__ ~) \--______________--~~
* //.-~~~-~_--~- |-------~~~~~~~~
* //.-~~~--\
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* God beast bless never BUG
*/
const int MAX=12;
int a[MAX];
map<char,int>mp;
int ans;
void permutation(char *str,int length)
{
sort(str,str+length);
do
{
// for(int i=0; i<length; i++)
// {
// printf("%c ",str[i]);
// }
// printf("\n");
for(int i=0;i<length;i++){
mp[str[i]]=i;
}
// for(int i=0;i<length;i++){
// cout<<str[i]<<"--"<<mp[str[i]]<<endl;
// }
int flag=1;
for(int i=0;i<length;i++){
if(a[i]!=i+1){
if(mp[i+1+'0']>mp[a[i]+'0'])
flag=0;
}
}
if(flag) ans++;
}
while(next_permutation(str,str+length));
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
char str[10];
for(int i=0;i<n;i++){
str[i]='1'+i;
}
permutation(str,n);
cout<<ans;
return 0;
}
Explosive search
/*
*@Author: GuoJinlong
*@Language: C++
*/
//#include <bits/stdc++.h>
/*
* __----~~~~~~~~~~~------___
* . . ~~//====...... __--~ ~~
* -. \_|// |||\\ ~~~~~~::::... /~
* ___-==_ _-~o~ \/ ||| \\ _/~~-
* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~
* _-~~ .=~ | \\-_ '-~7 /- / || \ /
* .~ .~ | \\ -_ / /- / || \ /
* / ____ / | \\ ~-_/ /|- _/ .|| \ /
* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\
* ' ~-| /| |-~\~~ __--~~
* |-~~-_/ | | ~\_ _-~ /\
* / \ \__ \/~ \__
* _--~ _/ | .-~~____--~-/ ~~==.
* ((->/~ '.|||' -_| ~~-/ , . _||
* -_ ~\ ~~---l__i__i__i--~~_/
* _-~-__ ~) \--______________--~~
* //.-~~~-~_--~- |-------~~~~~~~~
* //.-~~~--\
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* God beast bless never BUG
*/
const int MAX=15;
int vis[MAX];
int n;
int a[MAX];
int in[MAX];
int ans;
void dfs(int pos){
if(pos==n){
ans++;
return;
}
for(int i=1;i<=n;i++){
if(!vis[i]&&!in[i]){
vis[i]=1;
if(a[i]!=i) in[a[i]]--;
dfs(pos+1);
vis[i]=0;
if(a[i]!=i) in[a[i]]++;
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]!=i) in[a[i]]++;
}
dfs(1);
cout<<ans<<endl;
}