1.游戏（单调队列）
注意如果结果是分数，直接设置变量为double，最好不要使用把int类型乘1.0变成分数来计算。
#include <iostream>
#include <queue>
using namespace std;
const int N=1e5+10;
//滑动窗口大小为k,最大值为P,最小值为Q,K=P-Q
//窗口个数为cnt=n-k+1
//所有情况为all=cnt*cnt
//期望值为(K1+K2+...+Kall)/all
//由于熊大选框和熊二选框的情况是一样的，因此只需要
//(K1+K2+...+Kcnt)/cnt
int a[N];
int wd[N];
deque<int>q;//双端队列
int main()
{
int n,k;
scanf("%d %d\n",&n,&k);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
double sump=0;//窗口最大值加和
for(int i=1;i<=n;i++)
{
while(!q.empty()&&a[q.back()]<a[i])q.pop_back();
q.push_back(i);//4 3 2 1...(从大到小的窗口)a[i]<=a[q.back()]才加入
if(i>=k)//大于等于窗口大小才开始计算答案
{ //不在窗口内的下标pop掉
while(!q.empty()&&q.front()<=i-k)q.pop_front();
sump+=a[q.front()];
}
}
q.clear();//注意要把队列清空！
double sumq=0;//窗口最小值加和
for(int i=1;i<=n;i++)
{
while(!q.empty()&&a[q.back()]>a[i])q.pop_back();
q.push_back(i);//1 2 3 4...(从小到大的窗口)a[i]>=a[q.back()]才加入
if(i>=k)//大于等于窗口大小才开始计算答案
{ //不在窗口内的下标pop掉
while(!q.empty()&&q.front()<=i-k)q.pop_front();
sumq+=a[q.front()];
}
}
printf("%.2lf\n",(sump-sumq)/(n-k+1));
return 0;
}2.01游戏（DFS剪枝）
#include<iostream>
using namespace std;
char a[15][15];
bool flag=0;
int n;
bool check()
{
//判断行
for(int i=0;i<n;i++)
{
int cnt0=0,cnt1=0;//记录连续出现
int sum0=0,sum1=0;
for(int j=0;j<n;j++)
{
if(a[i][j]=='_')cnt1=0,cnt0=0;//连续中断
else if(a[i][j]=='1'){
cnt1++;
sum1++;
cnt0=0;
}else if(a[i][j]=='0'){
cnt0++;
sum0++;
cnt1=0;
}
if(cnt1>2||cnt0>2)return 0;
if(sum1>n/2||sum0>n/2) return false;//超过一半就无法保证数量相等
}
}
//判断列
for(int i=0;i<n;i++)
{
int cnt0=0,cnt1=0;//记录连续出现
int sum0=0,sum1=0;
for(int j=0;j<n;j++)
{
if(a[j][i]=='_')cnt1=0,cnt0=0;//连续中断
else if(a[j][i]=='1'){
cnt1++;
sum1++;
cnt0=0;
}else if(a[j][i]=='0'){
cnt0++;
sum0++;
cnt1=0;
}
if(cnt1>2||cnt0>2)return 0;
if(sum1>n/2||sum0>n/2) return false;//超过一半就无法保证数量相等
}
}
return 1;
}
void dfs(int x,int y)//默认是先向右走再向下走
{
if(flag)return;
if(y==n)
{
x++;//再向下
y=0;//再从左边起始开始
}
if(x==n)
{
//到达右下角了可以输出答案
flag=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cout<<a[i][j];
}
cout<<endl;
}
return;
}
if(a[x][y]=='_')
{
a[x][y]='1';
if(check())dfs(x,y+1);//合法才继续往下搜
if(flag)return;
a[x][y]='0';
if(check())dfs(x,y+1);//合法才继续往下搜
if(flag)return;
a[x][y]='_';//复原
}else dfs(x,y+1);
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>a[i][j];
}
}
dfs(0,0);
return 0;
}3.子2023（动态规划）
#include <iostream>
#include <string>
using namespace std;
long long dp[4];//注意开longlong!!
//dp[0]:以2结尾的序列数量
//dp[1]:以20结尾的序列数量
//dp[2]:以202结尾的序列数量
//dp[3]:以2023结尾的序列数量
int main()
{
string s;
for(int i=1;i<=2023;i++)
{
string str=to_string(i);
s+=str;
}
for(int i=0;i<s.size();i++)
{
if(s[i]=='2')
{
dp[0]++;
dp[2]=dp[2]+dp[1];
}else if(s[i]=='0')
{
dp[1]=dp[1]+dp[0];
}else if(s[i]=='3')
{
dp[3]=dp[3]+dp[2];
}
}
cout<<dp[3];
return 0;
}4.双子数（质因数分解，线性筛）
#include <iostream>
#include <cmath>
using namespace std;
#define ll long long
const ll N=1e7+9;//N*N>23333333333333(2.3*10^13)
ll prime[N];
ll ans;
bool st[N];
//线性筛O(n)
ll getPrime()
{
ll cnt=0;
for(ll i=2;i<=N;i++)
{
if(!st[i])prime[cnt++]=i;
for(ll j=0;prime[j]*i<=N;j++)
{
st[prime[j]*i]=1;
if(i%prime[j]==0)break;
}
}
return cnt;
}
int main()
{
ll idx=getPrime();//预处理得到素数
for(ll i=0;i<idx;i++)//遍历所有素数
{
ll p2=prime[i]*prime[i];//p^2
if(p2*p2>23333333333333)break;
for(ll j=i+1;j<idx;j++)
{
ll q2=prime[j]*prime[j];//q^2
if(p2*q2>23333333333333)break;
if(p2*q2<2333)continue;
ans++;//在区间内
}
}
cout<<ans<<endl;
return 0;
}5.合并数列（双指针）
#include <iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int b[N];
int n,m;
int ans;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>b[i];
int i=0,j=0;//从0开始
//采用前缀和的思想
int cnta=0,cntb=0;
while(i<=n&&j<=m)
{
if(cnta==cntb)//注意相等是等号!
{
cnta=a[++i];
cntb=b[++j];
}
else if(cnta<cntb)
{
cnta+=a[++i];
ans++;
}
else if(cntb<cnta)
{
cntb+=b[++j];
ans++;
}
}
cout<<ans<<endl;
return 0;
}
6.数三角形（枚举，STL）
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
using namespace std;
#define ll long long
#define pii pair<int,int>
int main()
{
int n;
cin>>n;
vector<pii>a(n+2);
map<pii,int>m;//表示坐标(x,y)点一共出现了几次
for(int i=1;i<=n;i++)
{
cin>>a[i].first>>a[i].second;
m[{a[i].first,a[i].second}]++;
}
int ans=0;
for(int i=1;i<=n;i++)//枚举每个点作为顶点
{
map<ll,vector<int>>st;//距离到达为ll时有多少个点
for(int j=1;j<=n;j++)
{
ll dist=(a[i].first-a[j].first)*(a[i].first-a[j].first)+
(a[i].second-a[j].second)*(a[i].second-a[j].second);
if(dist!=0)st[dist].push_back(j);//已经保证了i!=j
}
//计算合法数量
for(auto &x:st)//st为map类型
{
vector<int>&v=x.second;
int cnt=v.size();
ans+=cnt*(cnt-1)/2;//两两组合可以作为答案
//保证三点不共线
int del=0;//不合法的点的数量
for(int j=0;j<v.size();j++)
{
int x1=a[i].first,y1=a[i].second;
int x2=a[v[j]].first,y2=a[v[j]].second;
int x3=2*x1-x2,y3=2*y1-y2;//三点共线，都在一个圆内
//x1=(x3+x2)/2,y1=(y3+y2)/2
del+=m[{x3,y3}];
}
ans-=(del/2);//三点共线 两点的情况多计算了一次
}
}
cout<<ans<<endl;
return 0;
}7.AB路线（BFS）
#include <iostream>
#include <queue>
using namespace std;
#define ll long long
const int N=1000+500;
char a[N][N];
int n,m,k;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
ll vis[N][N][11],dis[N][N][11];
//因为一个位置可以重复走多次，
//再加一维（到这个位置是第几个字母）
struct node
{
int x,y,cnt;
//cnt为当前为第cnt个相同字母
node(int x=0,int y=0,int cnt=0):x(x),y(y),cnt(cnt){}
};
queue<node>q;//用于bfs
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
q.push(node(1,1,1));//cnt=1,为第一个相同字母
vis[1][1][1]=1;
if(n==1&&m==1)//特判
{
cout<<0<<endl;
return 0;
}
//开始BFS
while(!q.empty())
{
node t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int xx=t.x+dx[i];
int yy=t.y+dy[i];
int cc=t.cnt+1;
if(xx<1||xx>n||yy<1||yy>m)continue;
if(cc>k)//需要变
{
if(a[t.x][t.y]==a[xx][yy])continue;
else cc=1;
}
else //不需要变
{
if(a[t.x][t.y]!=a[xx][yy])continue;
}
if(vis[xx][yy][cc]!=0)continue;
vis[xx][yy][cc]++;
dis[xx][yy][cc]=dis[t.x][t.y][t.cnt]+1;
if(xx==n&&yy==m)//BFS先找到的一定是最小的，直接输出
{
cout<<dis[xx][yy][cc]<<endl;
return 0;
}
q.push(node{xx,yy,cc});
}
}
return 0;
}8.跑步计划（日期问题）
#include <iostream>
#include <string>
using namespace std;
int main()
{
int ans=0;
int a[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
if((2023%400==0)||(2023%4==0&&2023%100!=0))a[2]++;
int days=0;
for(int i=1;i<=12;i++)
{
for(int j=1;j<=a[i];j++)
{
days++;
string s1=to_string(i);
string s2=to_string(j); //2023年1月1日是周日
if(s1.find('1')!=-1||s2.find('1')!=-1||days%7==2)ans+=5;
else ans++;
}
}
cout<<ans<<endl;
return 0;
}9.火车运输（动态规划背包问题）
#include <iostream>
using namespace std;
const int N=1000+10;
int dp[N][N];
int w[N];
int n,a,b;
int main()
{
cin>>n>>a>>b;
for(int i=1;i<=n;i++)cin>>w[i];
// 三种情况：不选，放A，放B
for(int i=1;i<=n;i++)
{
for(int j=a;j>=0;j--)
{
for(int k=b;k>=0;k--)
{
if(j-w[i]>=0)dp[j][k]=max(dp[j][k],dp[j-w[i]][k]+w[i]);
if(k-w[i]>=0)dp[j][k]=max(dp[j][k],dp[j][k-w[i]]+w[i]);
}
}
}
cout<<dp[a][b]<<endl;
return 0;
}10.走方格（动态规划图论）
#include <iostream>
using namespace std;
const int N=1000+100;
int a[N][N];
int dp[N][N];
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
cin>>a[i][j];
}
}
for(int i=0;i<n;i++)
{
dp[i][0]=i;//表示走到此步需要的时间
//因为连续的跳步只发生在水平方向
}
for(int i=0;i<n;i++)
{
for(int j=1;j<n;j++)
{
dp[i][j]=1e9;//初始为大值
// 从上面下来
if(i>0)dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
// 向左到达最远的地方(即最小的地方)
// 因为是从上到下，从左到右枚举，所以是向左（因为左边已是更新好的值）
int temp=j;//临时变量
while(a[i][temp]<a[i][temp-1]&&temp>=1)//严格小于
{
dp[i][j]=min(dp[i][j],dp[i][temp-1]+1);
temp--;
}
//从左边一个过来
dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
}
}
cout<<dp[n-1][n-1]<<endl;
return 0;
}11.选段排序（堆，贪心）
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int a[N];
priority_queue<int,vector<int>>q1;//大顶堆
priority_queue<int,vector<int>,greater<int>>q2;//小顶堆
int main()
{
int n,p,q;
cin>>n>>p>>q;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+p,a+1+q);//注意sort的区间！！
for(int i=p;i<=q;i++)
{
//区间[p,q]先放入
q1.push(a[i]);//大
q2.push(a[i]);//小
}
int ans=a[q]-a[p];//先得到初始的答案
//拓展右区间由[p,q]到[p,n]
int maxx=a[q];
int minn=a[p];
for(int i=q+1;i<=n;i++)
{
int t=q1.top();//先取堆顶
if(a[i]<minn)minn=a[i];//小的肯定可以排序到p
if(a[i]<t)//t是拓展时用的
{
q1.pop();//保证队列元素在[p,q]中
q1.push(a[i]);
ans=max(ans,q1.top()-minn);
}
}
//拓展左区间由[p,q]到[1,q],向左减法
for(int i=p-1;i>=1;i--)
{
int t=q2.top();//先取堆顶
if(a[i]>maxx)maxx=a[i];//大的肯定可以排序到q
if(a[i]>t)
{
q2.pop();//保证队列元素在[p,q]中
q2.push(a[i]);
ans=max(ans,maxx-q2.top());
}
}
cout<<ans<<endl;
return 0;
}12.混乘数字（数学，枚举）
#include <iostream>
#include <string>
#include <map>
#include <set>
using namespace std;
#define ll long long
set<ll>ans;//自动去重
bool check(ll n,ll a,ll b)
{
int num[10]={0};
string sn=to_string(n);
string sa=to_string(a);
string sb=to_string(b);
for(int i=0;i<sn.size();i++)
{
num[sn[i]-'0']++;
}
for(int i=0;i<sa.size();i++)
{
num[sa[i]-'0']--;
}
for(int i=0;i<sb.size();i++)
{
num[sb[i]-'0']--;
}
for(int i=0;i<=9;i++)
{
if(num[i])return false;//通过相减
}
return true;
}
int main()
{
for(ll i=1;i<=1000000;i++)
{
ll kk=i*i;
if(kk>1000000)break;
if(check(kk,i,i))ans.insert(kk);
for(ll j=i+1;j<=1000000;j++)
{
kk=i*j;
if(kk>1000000)break;
if(check(kk,i,j))ans.insert(kk);
}
}
cout<<ans.size()<<endl;
return 0;
}13.X质数（线性筛，二进制）
#include <iostream>
#include <string>
using namespace std;
const int N=1e6;
int idx=0;
int prime[N];
int st[N];
int ans=0;
void get()
{
st[0]=st[1]=1;
for(int i=2;i<=N;i++)
{
if(!st[i])prime[++idx]=i;
for(int j=1;j<=idx&&i*prime[j]<=N;j++)//从1开始
{
st[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
bool check(int x) {
string num = to_string(x);
int n = num.size();// n个数字，每个数字算不算进去两种选择
for (int i = 0; i < (1 << n); ++i) { //n位数，有2^n种情况
int cur = 0;
for (int j = 0; j < n; ++j) { // 每种情况为一个二进制值
if ((i >> j) & 1) cur = cur * 10 + num[j] - '0';
}
if (!st[cur]) return true;
}
return false;
}
int main()
{
get();
for(int i=1;i<=N;i++)
{
if(check(i))ans++;
}
cout<<ans<<endl;
return 0;
}
