EOJ Monthly 2020.7 Sponsored by TuSimple（A 签到 B 签到 C 思维+二维前缀和 E dfs 构造）

题目链接

A. 打字机

做法：签到题，对b进行 a 的匹配。类似括号匹配的做法。若有匹配则看最后一个b的前面a的数量是否比b 是 输出 Happy Fang否 输出 Sad Fang。

若匹配失败 输出 Dead Fang 。

特判断全a的情况

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb emplace_back
#define pii pair<int,int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
inline ll read()
{ll x=0,w=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}return w==1?x:-x;
}
const int N=1e6+10;
char s[N];
int dp[N][2];
int main()
{int _ =read();while(_--){scanf("%s",s+1);int len = strlen(s + 1);rep(i,1,len){rep(j,0,1) dp[i][j]=dp[i-1][j];if(s[i]=='a') dp[i][0]++;else dp[i][1]++;}if(dp[len][1]==0){puts("Happy Fang");continue;}int flag=1,f=0;for(int i=len;i>=1;--i){if(s[i]=='b'){if(dp[i][0]>dp[i][1]) f=1;if(dp[i][0]<dp[i][1]) flag=0;break;}}int num=0;for(int i=1;i<=len&&flag;++i){if(s[i]=='a') num++;else {if(num) num--;else flag=0;}}if(flag){if(!f) puts("Happy Fang");else puts("Sad Fang");}else puts("Dead Fang");}
}

B. 线上考试

签到题。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb emplace_back
#define pii pair<int,int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
inline ll read()
{ll x=0,w=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}return w==1?x:-x;
}
int main()
{int n =read();int ans = 0;rep(i,1,n){string s;int x;cin>>s>>x;if(s[0]=='S') ans=max(ans,x);else ans=max(ans,(1<<x)-1);}cout<<ans<<endl;
}

C. OLED

做法：对矩阵屏保 的每一个1 计算 他能在屏幕中对所有 位置的贡献（+1）。然后取屏幕中贡献值最大的为100.  其他按照贡献值比例 乘 100即可。二维前缀和 即可

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb emplace_back
#define pii pair<int,int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
inline ll read()
{ll x=0,w=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}return w==1?x:-x;
}
ll dp[4000][2200];
int n,m,a,b;
ll c[4000][2200];
int main()
{a = read(), b = read(), n = read(), m = read();rep(i, 1, a) rep(j, 1, b) c[i][j] = read();rep(i, 1, a) {rep(j, 1, b) {if(c[i][j]) {int l=n-(a-i+1)+1;int r=m-(b-j+1)+1;dp[i][j]++;dp[i][r+1]--;dp[l+1][j]--;dp[l+1][r+1]++;//printf("i:%d j:%d l:%d r:%d\n", i, j, l, r);}}}ll ans=0;rep(i, 1, n){rep(j, 1, m){dp[i][j]+=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];ans=max(ans,dp[i][j]);}}//    rep(i, 1, n)
//    {
//        rep(j, 1, m) {
//            printf("%lld ",dp[i][j]);
//        }
//        puts("");
//    }rep(i, 1, n){rep(j, 1, m) {printf("%lld ",(dp[i][j]*100)/ans);}puts("");}}
/*
2 2 4 4
1 0
0 0
*/

E. 因数串

做法：很显然是 各自素数 的 幂次方 组合一下，每次 每个幂方 之和 大小 改变为1

对于样例：

可以得到一个规律：dfs时，每个素数的幂次方 是 先增  后 减 再增的。于是记录每个素数当前版本值。版本值 为偶数时 幂次方的值就递增。奇数就递减。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define per(i,a,b) for(int i=a;i>=(b);--i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb emplace_back
#define pii pair<int,int>
#define mk make_pair
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
inline ll read()
{ll x=0,w=1; char c=getchar();while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}return w==1?x:-x;
}
const int N=20;
int n;
ll dp[N][62];
int num[N];
int t[N];
deque<ll>G[200];
void dfs(int id,ll now,int flag,int pre)
{if(id>n) {G[flag].push_back(now);printf("%lld\n",now);return ;}//printf("id:%d dp:%lld\n",id,dp[id][1]);if(t[id]%2==0){for(int i=0;i<=num[id];++i){dfs(id+1,now*dp[id][i],flag+i,i);}t[id]++;}else{for(int i=num[id];i>=0;--i){dfs(id+1,now*dp[id][i],flag+i,i);}t[id]++;}}
int main()
{n=read();rep(i,1,n) dp[i][0]=1,dp[i][1]=read(),num[i]=read();rep(i,1,n){rep(j,2,num[i]) dp[i][j]=dp[i][j-1]*dp[i][1];}dfs(1,1,0,0);}