抓娃娃
思路：记线段的中点mid=(l+r)/2。注意到当L<=mid<=R时（即2L<=(l+r)<=2R），则区间[L,R]框住了线段，那么我们可以使用前缀和来解决。输入线段l r时，我们让a[l+r]++。计算前缀和后，当查询时我们查询区间[2L,2R]有多少条线段即可。
#include <bits/stdc++.h>
#define int long long
const int N=2e6+10;
using namespace std;
int n,m;
int a[N];
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++){int l,r;cin>>l>>r;a[l+r]++;}for(int i=1;i<=2e6;i++) a[i]=a[i]+a[i-1];for(int i=1;i<=m;i++){int l,r;cin>>l>>r;cout<<a[2*r]-a[2*l-1]<<'\n'; }return 0;
} 跑步计划
#include <bits/stdc++.h>
#define int long long
const int N=2e6+10;
using namespace std;
int d[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool check(int y,int d,int now)
{bool f=0;while(y){int x=y%10;y/=10;if(x==1) f=1;}while(d){int x=d%10;d/=10;if(x==1) f=1;}if(now%7==0) f=1;return f;
}
signed main()
{int now=6;int ans=0;for(int i=1;i<=12;i++)for(int j=1;j<=d[i];j++){if(check(i,j,now)) ans+=5;else ans+=1;now=(now+1)%7;}cout<<ans<<'\n';
} 01游戏
#include<bits/stdc++.h>
const int N=15;
using namespace std;
int n;
char g[N][N];
int cstate[N];//保存每列的状态
int visr[1<<15],visc[1<<15];//行、列状态出现的次数
bool check(int x,int y)//检查行列连续3个字符
{int num=1;for(int i=1;x-i>=0&&g[x][y]==g[x-i][y];i++){num++;if(num>2) return 0;} num=1;for(int i=1;y-i>=0&&g[x][y]==g[x][y-i];i++){num++;if(num>2) return 0;}return 1;
}
bool check_row(int x)//检查行01个数
{int num=0;for(int j=0;j<n;j++)if(g[x][j]=='1') num++;return num==n/2;
}
bool check_col(int y)//检查列01个数
{int num=0;for(int i=0;i<n;i++)if(g[i][y]=='1') num++;return num==n/2;
}
void dfs(int x,int y,int rstate)
{if(x==n)//填完了 {bool ok=1;for(int j=0;j<n;j++){visc[cstate[j]]++;if(visc[cstate[j]]>=2) ok=0;}for(int j=0;j<n;j++)visc[cstate[j]]=0;if(!ok) return ;for(int j=0;j<n;j++)if(!check_col(j)) return ;for(int i=0;i<n;i++){for(int j=0;j<n;j++)cout<<g[i][j];cout<<'\n';}exit(0);}else{if(g[x][y]=='_'){int old=cstate[y];//保存原状态 g[x][y]='1';cstate[y]|=(1<<x);//记录列的状态 if(check(x,y)){if(y+1<n){dfs(x,y+1,rstate|(1<<y));}else{int newr=rstate|(1<<y);if(!visr[newr]&&check_row(x)){visr[newr]++;dfs(x+1,0,0);visr[newr]--;}}}cstate[y]=old;//恢复列的状态 g[x][y]='_';g[x][y]='0';cstate[y]|=(0<<x);//if(check(x,y)){if(y+1<n){dfs(x,y+1,rstate|(0<<y)); } else{int newr=rstate|(0<<y);if(!visr[newr]&&check_row(x)){visr[newr]++;dfs(x+1,0,0);visr[newr]--;}}} cstate[y]=old;g[x][y]='_';}else{int old=cstate[y];int num=g[x][y]-'0';cstate[y]|=(num<<x);if(check(x,y)){if(y+1<n){dfs(x,y+1,rstate|(num<<y));}else{int newr=rstate|(num<<y);if(!visr[newr]&&check_row(x)){visr[newr]++;dfs(x+1,0,0);visr[newr]--;}}}
// cstate[y]=old;}}
}
signed main()
{cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>g[i][j];dfs(0,0,0); return 0;
} 钉板上的正方形
思路：枚举四个顶点是不好判断的。我们可以枚举左上的点和左下的点，然后根据正方形的性质去找到另外两个点，再判断这两个是否存在即可。注意：不用开根号避免精度问题。
#include<bits/stdc++.h>
const int N=15;
using namespace std;
int g[10][10]={
1,1,0,1,0,1,1,1,1,1,
1,1,1,0,0,1,1,1,1,0,
1,1,0,0,1,0,1,1,1,1,
1,0,1,1,0,1,1,1,1,0,
1,0,1,0,1,1,1,1,0,0,
1,0,0,1,0,1,0,1,0,1,
1,1,1,1,1,1,1,1,1,0,
0,1,1,1,1,1,1,1,1,0,
0,1,1,0,1,0,1,1,1,1,
1,0,1,0,0,1,0,1,0,0
}; signed main()
{set<int>s;for(int i=0;i<10;i++)for(int j=0;j<10;j++)if(g[i][j]){for(int k=i+1;k<10;k++)for(int p=0;p<=j;p++)if(g[k][p]){if(i+j-p<10&&j+k-i<10&&k+j-p<10&&p+k-i<10&&g[i+j-p][j+k-i]&&g[k+j-p][p+k-i]){s.insert((k-i)*(k-i)+(j-p)*(j-p)); }}}cout<<s.size()<<'\n';return 0;
}