EOJ Monthly 2020.7 Sponsored by TuSimple 部分题解

A. 打字机

题解：贪心
只需要寻找最后一个d的位置，判断之前a的个数与b的个数是否相等。
如果a大于b则Sad，等于则为Happy
注意：在遍历字符串的同时，对于任何一个位置从开始到当前位置的a和b的个数，a都不可以小于b，如果小于，则输出Dead。

#include <bits/stdc++.h>
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn=510;
using namespace std;


int main()
{
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        int ansa=0,ansb=0,tag=0,xxx=0;
        for(int i=0;i<s.size();i++){
            if(s[i]=='a') ansa++,tag++;
            else xxx=ansa,ansb++,tag--;
            if(tag==-1) break;
        }
        if(tag!=-1){
            if(xxx==ansb||ansb==0) cout<<"Happy Fang\n";
            else cout<<"Sad Fang\n";
        }
        else cout<<"Dead Fang\n";
    }
    return 0;
}

B.线上考试

题解：
找出没个题所有答案可能的情况，输出最大值
1.单选题，没得说，有多少选项就有几种情况
2.多选题，可以用排列组合Cn m来做把所有组合情况加起来即可

代码：

#include <bits/stdc++.h>
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn=510;
using namespace std;

ll a[20];
void init(){
    a[1]=1,a[0]=1;
    for(int i=2;i<=12;i++){
        a[i]=a[i-1]*i;
    }
}

int C(int n,int m){
    return (a[n]/a[n-m])/a[m];
}

int main()
{
    init();
    //for(int i=0;i<=10;i++) cout<<a[i]<<endl;
    int n,x;
    cin>>n;
    char s[10];
    ll imax=MinN;
    while(n--){
        scanf("%s",s);
        scanf("%d",&x);
        if(s[0]=='S') imax=max(imax,(ll)x);
        else{
            ll ans=0;
            for(int i=1;i<=x;i++){
                ans+=C(x,i);
                //cout<<ans<<endl;
            }
            imax=max(imax,ans);
        }
    }
    cout<<imax<<endl;
    return 0;
}

C.OLED

题解：
二维差分
因为概率相同，那么我们可以假设这个屏保图案，在所有可能会出现的地方都出现一次，每个像素点在某个位置，我们就在那个位置+1即可。
例如样例一：
1 2 4 3
0 1

0 100 100
0 100 100
0 100 100
0 100 100
我们不难发现，图案（1，2）这个地方有个像素点，他会在区域
i-----n-x+i
j-----m-y+j
（表示的是一个矩形）
都出现一次，所以我们要在这个范围内都加1，所以我们用二维差分在O(1)时间复杂度的情况下给他区域+1。

最后找出区域出现最多的那个点，输出100，其他点就是(b[i][j]/max)×100向下取整

#include <bits/stdc++.h>
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn=510;
using namespace std;
int b[3850][2170];
void insert(int x1, int y1, int x2, int y2, int c)
{
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main()
{
    int n,m,x,y;
    cin>>x>>y>>n>>m;
    for(int i=1;i<=x;i++){
        for(int j=1;j<=y;j++){
            int temp;
            scanf("%d",&temp);
            if(temp==1){
                //cout<<n-x+i<<" "<<m-y+j<<endl;
                insert(i,j,n-x+i,m-y+j,1);
            }
        }
    }
    int imax=MinN;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
            imax=max(imax,b[i][j]);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(b[i][j]==imax){
                printf("100 ");
            }
            else printf("%d ",(int)(((double)b[i][j]/(double)imax)*100));
        }
        printf("\n");
    }
}