7. 回文日期

//关键在于判断月份在1-12之间，天数不能越界
//注意特例 11111110 的结果，故循环得从本身b值开始
#include<bits/stdc++.h>
using namespace std;
int months[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};

int judge(int x){
    if(x % 4==0&&x % 100!=0 || x % 400==0) return true;
    return false;
} 

int main()
{
    int a,m,d;
    cin >> a;
    int b=a/10000;
    for(int i = b;;i++){//回文数字 20200202 
        if(judge(i)) months[2]++;
         m = (i%10) *10 + i/10 %10;
         d = (i/100%10)*10+i/1000;
         if(months[m] >= d && m>=1 && m<=12){
            int year1 = i*10000+m*100+d;
            if(year1==a) continue;
            cout<<year1<<endl;
            break;
         }
    if(months[2]==29) months[2]--;//记得回溯回来 ，否则闰年的二月一直在增加 
    }

    for(int i = b;;i++){//输出 ABABBABA 型 
        if((i%100) != i/100 || (i/1000)==(i/100%10)) continue;
        if(judge(i)) months[2]++;
         m = (i%10) *10 + i/10 %10;
         d = (i/100%10)*10+i/1000;
         if(months[m] >= d && m>=1 && m<=12){
            int year2 = i*10000+m*100+d;
            if(year2==a) continue;
            cout<<year2<<endl;
            break;
         }
    if(months[2]==29) months[2]--;       
    } 
}

8. 子串分值和

参考题解
参考题解

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
string a;
int f[N];
//纯暴力 (待补充完善) 
int main()
{
    cin>>a;
    int sum=0;
    for(int i=0;i<a.size();i++){
        map<char,int>p;
        memset(f,0,sizeof f);
        for(int j=i;j<a.size();j++) {


            if(!p[a[j]]) f[j+1]=f[j]+1;
            else f[j+1]=f[j];
            sum+=f[j+1];
            p[a[j]]=1;
        }
    }
        cout<<sum<<endl;
        return 0;
}

//分析之前的字符给予的贡献
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 7;
int vis[N], next[N];
LL ans = 0, sum = 0, now = 0;
string str;
int main()
{
    ios::sync_with_stdio(false);
    cin >> str;
    memset(vis, -1, sizeof(vis));
    memset(next, 0, sizeof(next));
    for(int i = 0; i < str.length(); i++)
    {
        if(vis[str[i] - 'a'] == -1)
        {
            now++;
            sum += now;
            vis[str[i] - 'a'] = i;
        }
        else
        { 
            sum += now;
            int lastPos = vis[str[i] - 'a'];
            next[lastPos] = i - vis[str[i] - 'a']; //重复出现的字符离最右边相同字符的距离 
            vis[str[i] - 'a'] = i;
        } 
    }
//  cout << sum << endl;
    ans += sum;
    int n = str.length();
    for(int i = 1; i < str.length(); i++)
    {
        if(!next[i-1]) //第i-1个字符是唯一的
        {
            sum = sum - (n - (i - 1));
            ans += sum;
        } 
        else
        {
            int dis = next[i-1]; //算出第i-1个字符与它相同的下一个字符的距离 
            sum = sum - dis;
            ans += sum;
        } 
    }
    cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
ll pre[30];
string s;

int main()
{
    IOS;
    cin>>s;
    ll len=s.length();
    s="0"+s;//下标从1开始
    ll ans=0;
    for(ll i=1;i<=len;i++){
        ans+=(i-pre[s[i]-'a'])*(len-i+1);
        cout<<ans<<"==="<<endl; 
        pre[s[i]-'a']=i;
    }   
    cout<<ans<<endl;
    return 0;
}

D:数的分解
本题总分：10分
【问题描述】
把 2019分解成 3个各不相同的正整数之和，并且要求每个正整数都不包
含数字2和4，一共有多少种不同的分解方法？
注意交换 3个整数的顺序被视为同一种方法，例如 1000+1001+18和
1001+1000+18被视为同一种。

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


int check(int n){
    while(n){
        int t = n %10;
        if(t == 2 || t == 4) return 0;
        n/=10;
    }
    return 1;
}
int main(){
    int ans = 0;

    for(int i=1;i<2019;i++){
        if(!check(i)) continue;
        for(int j=i+1;j<2019;j++){//排除顺序的问题
            if(!check(j)) continue;
            for(int k=j+1;k<2019;k++){
                if(!check(k)) continue;
                if(i+j+k==2019) ans++;
            }
        }
    }   
    cout<<ans<<endl;
    return 0;
}

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


int judge(int n){
    while(n){
        int t = n %10;
        if(t == 2 || t == 4) return 0;
        n/=10;
    }
    return 1;
}
int main(){
    int sum=0;

    for(int i = 1;i < 2019;i++){
        for(int j = 1;j < 2019;j++){
            for(int k = 1;k <2019;k++){
                if(i+j+k==2019 && judge(i) && judge(j) && judge(k)){
                    if(i!=j && j!=k &&k!=i) sum++;
                }
            }
        }
    }
    cout<<sum/6<<endl;//除去顺序交换的情况 
    return 0;
}

E.迷宫
下图给出了一个迷宫的平面图，其中标记为1 的为障碍，标记为0 的为可以通行的地方。

F.特别数的和

 #include<bits/stdc++.h>
using namespace std;
/*
 2、0、1、9 的数字很感兴趣（不包括前导 0），

 */

int check(int n){
    while(n){
       int t =n%10;
       if(t == 2 || t==0 || t==1 ||t==9) return 1;
       n/=10;
    }
    return 0;

}


int main(){
    int n,sum=0;
    cin >> n;
    for(int i=1;i<=n;i++){
        int t = i;
        if(check(t)) sum+=i;
    }
    cout<<sum<<endl;
    return 0;
} 

G.完全二叉树的权值

 #include<bits/stdc++.h>
using namespace std;
int q[100005];
typedef long long ll;

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <=n; i++) 
        cin >> q[i];
    int maxx =-1;
    int deepth = 1;
    int res = 1;
    for(int i = 1; i <= n; i *= 2){
        long long s = 0;
        for(int j = i;  j <=  i*2 - 1 && j <= n; j ++) {
            s += q[j];
        }
        if(s > maxx) {
            maxx = s;
            res = deepth;
        }
        deepth++;
    }
    cout << res;
}

I.后缀表达式

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

 //本题可以添加括号，因为求最大值，可以使负的变成正的
 const int N=1e5+10;
 int a[2*N];

int main()
{
    int n,m;
    cin >> n>>m;
    int k=m+n+1;
    for(int i=1;i<=k;i++) cin >>a[i];

    sort(a+1,a+1+k);

    ll sum=0;
    if(m==0) {//都是加号
        for(int i=1;i<=k;i++) sum+=a[i];
        cout<< sum<<endl;
        return 0;
    }
    else {
        sum+=a[k],sum-=a[1];
        for(int i=2;i<k;i++) sum+=abs(a[i]);
        cout<<sum<<endl;
    }

    return 0;
}

B.明码
汉字的字形存在于字库中，即便在今天，16点阵的字库也仍然使用广泛。
16点阵的字库把每个汉字看成是16x16个像素信息。并把这些信息记录在字节中。

一个字节可以存储8位信息，用32个字节就可以存一个汉字的字形了。
把每个字节转为2进制表示，1表示墨迹，0表示底色。每行2个字节，
一共16行，布局是：

第1字节，第2字节
第3字节，第4字节
....
第31字节, 第32字节

这道题目是给你一段多个汉字组成的信息，每个汉字用32个字节表示，这里给出了字节作为有符号整数的值。

题目的要求隐藏在这些信息中。你的任务是复原这些汉字的字形，从中看出题目的要求，并根据要求填写答案。

这段信息是（一共10个汉字）：

4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0
16 64 16 64 34 68 127 126 66 -124 67 4 66 4 66 -124 126 100 66 36 66 4 66 4 66 4 126 4 66 40 0 16
4 0 4 0 4 0 4 32 -1 -16 4 32 4 32 4 32 4 32 4 32 8 32 8 32 16 34 16 34 32 30 -64 0
0 -128 64 -128 48 -128 17 8 1 -4 2 8 8 80 16 64 32 64 -32 64 32 -96 32 -96 33 16 34 8 36 14 40 4
4 0 3 0 1 0 0 4 -1 -2 4 0 4 16 7 -8 4 16 4 16 4 16 8 16 8 16 16 16 32 -96 64 64
16 64 20 72 62 -4 73 32 5 16 1 0 63 -8 1 0 -1 -2 0 64 0 80 63 -8 8 64 4 64 1 64 0 -128
0 16 63 -8 1 0 1 0 1 0 1 4 -1 -2 1 0 1 0 1 0 1 0 1 0 1 0 1 0 5 0 2 0
2 0 2 0 7 -16 8 32 24 64 37 -128 2 -128 12 -128 113 -4 2 8 12 16 18 32 33 -64 1 0 14 0 112 0
1 0 1 0 1 0 9 32 9 16 17 12 17 4 33 16 65 16 1 32 1 64 0 -128 1 0 2 0 12 0 112 0
0 0 0 0 7 -16 24 24 48 12 56 12 0 56 0 -32 0 -64 0 -128 0 0 0 0 1 -128 3 -64 1 -128 0 0

—------------------------------------分割线

//bitset的作用是把一个数转换成二进制
//bitset<8>是把一个数转换成一个8位的二进制
 #include<bits/stdc++.h>
 using namespace std;

int main()
{
   int x,y;
   while(scanf("%d%d",&x,&y))
   {
     bitset<8> t;
     t=x;
     cout<<t;
     t=y;
     cout<<t<<endl;
   }

    return 0; 
}

D 测试次数

x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。

x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。

如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。
特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。
如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n

为了减少测试次数，从每个厂家抽样3部手机参加测试。

某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？

E 快速排序
以下代码可以从数组a[]中找出第k小的元素。
它使用了类似快速排序中的分治算法，期望时间复杂度是O(N)的。
请仔细阅读分析源码，填写划线部分缺失的内容。

#include <stdio.h>

int quick_select(int a[], int l, int r, int k) {
    int p = rand() % (r - l + 1) + l;
    int x = a[p];
    {int t = a[p]; a[p] = a[r]; a[r] = t;}
    int i = l, j = r;
    while(i < j) {
    while(i < j && a[i] < x) i++;
        if(i < j) {
        a[j] = a[i];
        j–;
    }
    while(i < j && a[j] > x) j–;
        if(i < j) {
        a[i] = a[j];
        i++;
    }
}
    a[i] = x;
    p = i;
    if(i - l + 1 == k) return a[i];
    if(i - l + 1 < k) return quick_select( _____________________________ ); //填空
    else return quick_select(a, l, i - 1, k);
}

int main()
{
    int a[] = {1, 4, 2, 8, 5, 7, 23, 58, 16, 27, 55, 13, 26, 24, 12};
    printf("%d\n", quick_select(a, 0, 14, 5));
    return 0;
}

答案：a,i+1,r,k-(i-l+1)

F 递增三元组

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

const int N = 100005;
int a[N];
int b[N];
int c[N];

typedef long long ll;

int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >>a[i];
    for(int i = 1;i <= n;i++) cin >>b[i];
    for(int i = 1;i <= n;i++) cin >>c[i];

    sort(a+1,a+1+n);
    sort(b+1,b+1+n);    
    sort(c+1,c+1+n);

    ll sum=0;
    for(int i=1;i<=n;i++){//以b[i]来看
        ll x = (lower_bound(a+1,a+1+n,b[i])-a)-1;//找到比b[i]大
        ll y = n-(upper_bound(c+1,c+1+n,b[i])-c)+1;//找到比b[i]小
         sum+=x*y;
    }
    cout<<sum<<endl;
    return 0;
} 

I 全球变暖

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

const int N = 1010;

char a[N][N];
int vis[N][N];
int d[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
int flag,n;

void dfs(int x, int y){
    vis[x][y] = 1;      //标记这个'#'被搜过。注意为什么可以放在这里
    if(a[x][y+1]=='#' && a[x][y-1]=='#' && a[x+1][y]=='#' && a[x-1][y]=='#')
        flag = 1;       //上下左右都是陆地，不会淹没
    for(int i = 0; i < 4; i++){ //继续DFS周围的陆地
        int nx = x + d[i][0], ny = y + d[i][1];
      //if(nx>=1 && nx<=n && ny>=1 && ny<=n && vis[nx][ny]==0 && a[nx][ny]=='#') //题目说边上都是水，所以不用这么写了
        if(vis[nx][ny]==0 && a[nx][ny]=='#') //继续DFS未搜过的陆地，目的是标记它们
            dfs(nx,ny);
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> a[i][j];
    int ans = 0 ;
    for(int i = 1; i <= n; i++)  //DFS所有像素点
        for(int j = 1; j <= n; j++)
            if(a[i][j]=='#' && vis[i][j]==0){
                flag = 0;
                dfs(i,j);
                if(flag == 0)  //这个岛全部被淹
                    ans++;     //统计岛的数量
            }
    cout<<ans<<endl;
    return 0;
}