一、日期问题

暴力，大体把代码写出来了，细节漏洞有点多，导致没出结果

bool函数记得在每个不符合要求的地方都要返回false，不然就会默认返回true

用set存去重数组

#include<bits/stdc++.h>
using namespace std;

int num[100];
int d[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
set<int>s;

bool is_valid(int a1,int a2,int a3,int a4)//合法日期的判断 
{
    int mon=a1*10+a2;
    int day=a3*10+a4;
    for(int i=1;i<=12;i++)
        if(mon==i&&day>0&&day<=d[i])
            return true;
    return false;
} 

int main()
{
    int cnt=0;
    for(int i=0;i<100;i++)
        scanf("%d",&num[i]);
    for(int i=0;i<100;i++)
        if(num[i]==2)
            for(int j=i+1;j<100;j++)
                if(num[j]==0)
                    for(int k=j+1;k<100;k++)
                        if(num[k]==2)
                            for(int o=k+1;o<100;o++)
                                if(num[o]==3)
                                    for(int p=o+1;p<100;p++)
                                        for(int q=p+1;q<100;q++)
                                            for(int x=q+1;x<100;x++)
                                                for(int y=x+1;y<100;y++)
                                                    if(is_valid(num[p],num[q],num[x],num[y]))
                                                        s.insert(num[p]*1000+num[q]*100+num[x]*10+num[y]);
    printf("%d",s.size());
    return 0;
 } 

二、01串的熵

没写

三、冶炼金属

暴力没写成功，后面发现v好像是单调的，但是没时间写了

当时想的是找到v的一个大致范围，再在里面找符合要求的最大最小值，蠢了，这个时候就应该想到二分

二分

找左边界的时候判断当前值是否>=目标值

找右边界的时候判断当前值是否<=目标值

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;

int n;
struct node{
    int a;
    int b;
}js[N]; 

bool check(int v)
{
    //找左边界需要判断这个数是否>=目标值，也就是js[i].a/v<=js[i].b，因为j[i].a/v小了说明除多了，就是v大了
    //但是要所有的i都满足这个条件时才成立
    //所以取相反，每当有一个js[i].a/v>js[i].b，就取false 
    for(int i=0;i<n;i++)
        if(js[i].a/v>js[i].b)
            return false;
        return true;
}

bool check1(int v)
{
    for(int i=0;i<n;i++)
        if(js[i].a/v<js[i].b)
            return false;
    return true;
}

int main()
{
    int m,M;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d%d",&js[i].a,&js[i].b);
    int l=1,r=1e9;

    //找左边界点 
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid))
            r=mid;
        else
            l=mid+1;
    }   
    m=l;

    //找右边界点
    l=1,r=1e9;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(check1(mid))
            l=mid;
        else
            r=mid-1;    
    } 
    M=l;

    printf("%d %d",m,M);
    return 0;
}

四、飞机降落

dfs

#include<bits/stdc++.h>
using namespace std;
const int N=12;

struct node{
    int t;
    int d;
    int l;
}f[N];
int n;
bool st[N];

bool dfs(int u,int last)//u表示已经降落的飞机数量，last表示上一架飞机降落完毕的时间
{
    if(u==n)
        return true;

    //遍历所有飞机
    for(int i=1;i<=n;i++)
    {
        //如果没有飞并且可以飞 
        if(st[i]==false&&(f[i].t+f[i].d)>=last)
        {
            st[i]=true;
            int time;//开始降落的时间
            if(f[i].t>=last)    time=f[i].t;
            else    time=last; 
            if(dfs(u+1,time+f[i].l))    
                return true;

            st[i]=false;    
        }   
    } 

    return false; 
} 

int main()
{
    int T;
    scanf("%d",&T);
    for(int i=0;i<T;i++)
    {
        memset(st,0,sizeof st);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d%d",&f[i].t,&f[i].d,&f[i].l);
        if(dfs(0,0))    printf("YES\n");
        else    printf("NO\n");
    }
    return 0;
}

五、接龙数列

根本想不到用n减去最长接龙子序列…

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=1e9;

char s[M];
int a1[N];//首位 
int a2[N];//末位 
int dp[N];
//dp[i]表示以第i个字母结尾的接龙序列的长度
//属性：最大值 

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        a1[i]=s[0]-'0';
        a2[i]=s[strlen(s)-1]-'0';
    }

    //初始化
    for(int i=1;i<=n;i++)
        dp[i]=1;//每个元素都可以单独构成一个长度为1的接龙序列 

    for(int i=1;i<=n;i++)
    { 
        for(int j=1;j<i;j++)
        {
            //选 
            if(a1[i]==a2[j])
                dp[i]=max(dp[i],dp[j]+1);
        }
    }

    int M=0;
    for(int i=1;i<=n;i++)
        M=max(dp[i],M);
    printf("%d",n-M);
    return 0; 
} 

六、岛屿个数

bfs，不是很熟，记得多写几遍

#include<bits/stdc++.h>
using namespace std;
const int N=55;

typedef pair<int,int> PII;
queue<PII> q1;//岛屿
queue<PII> q;//海水 
int m,n;
char g[N][N];
bool st[N][N];//标记岛屿有没有被搜过 
int next4[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int next8[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
int cnt;

//岛屿bfs，四个方向
void bfs_(int a,int b)
{
    q1.push({a,b});
    st[a][b]=true;

    while(!q1.empty())
    {
        PII start=q1.front();//取出队首元素 
        q1.pop();//移除第一个元素 

        //往四个方向走
        for(int i=0;i<4;i++)
        {
            int x=start.first+next4[i][0],y=start.second+next4[i][1];
            if(x>=0&&x<=m+1&&y>=0&&y<=n+1&&st[x][y]==false)
                if(g[x][y]=='1')//如果是岛屿且没有搜过 
                {
                    st[x][y]=true;
                    q1.push({x,y});
                }   
        } 
    } 
} 

//海水bfs，八个方向 
void bfs(int a,int b)
{
    q.push({a,b});

    while(!q.empty())
    {
        PII start=q.front();
        q.pop();

        for(int i=0;i<8;i++)
        {
            int x=start.first+next8[i][0],y=start.second+next8[i][1];
            //如果没有越界且没有搜过 
            if(x>=0&&x<=m+1&&y>=0&&y<=n+1&&st[x][y]==false)
            {
                if(g[x][y]=='1')//如果是岛屿，就全部搜一遍 
                {
                    bfs_(x,y);
                    cnt++;
                }
                else//如果是海水就继续 
                {
                    st[x][y]=true; 
                    q.push({x,y});
                }
            }   
        }   
    }   
}

int main()
{
    int t;
    scanf("%d",&t);
    getchar();
    while(t--)
    {
        cnt=0;
        memset(g,'0',sizeof g);
        memset(st,0,sizeof st);
        scanf("%d%d",&m,&n);
        getchar();
        //读入地图 
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
                scanf("%c",&g[i][j]);
            getchar();
        }
        bfs(0,0);
        printf("%d\n",cnt);
    }
    return 0; 
 } 

七、字串简写

双指针是把i,j写在一个for里面，整个区间左右移动

千万别把strlen写在循环里面，会增加运行时间

一般方案数都要用longlong

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
typedef long long LL;

char c1,c2;
char s[N];
LL cnt; 
LL ans;

int main()
{
    int k;
    scanf("%d",&k);
    cin>>s>>c1>>c2;
    int n=strlen(s);

    for(int i=0,j=k-1;j<n;i++,j++)
    {
        if(s[i]==c1)
            cnt++;
        if(s[j]==c2)
            ans+=cnt;
    }
    printf("%lld",ans);
    return 0; 
 }