A. 老C的输入法

模拟一下就好了

#define int long long
string s,x[1009];
int n,ans;
string solve(string s){
    string str="";
    for(auto i:s){
        if(i>='a'&&i<='c')str+="2";
        else if(i>='d'&&i<='f')str+="3";
        else if(i>='g'&&i<='i')str+="4";
        else if(i>='j'&&i<='l')str+="5";
        else if(i>='m'&&i<='o')str+="6";
        else if(i>='p'&&i<='s')str+="7";
        else if(i>='t'&&i<='v')str+="8";
        else str+="9"; 
    }
    return str;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s,x[i]=solve(s);
    cin>>s;
    for(int i=1;i<=n;i++)if(x[i]==s)ans++;
    cout<<ans<<"\n";
}

B. coprime

nlogn 的 j += i

int gcd(int a,int b){ 
	return b==0 ? a : gcd(b,a%b); 
}
signed main() {  
	int n=read();  
	for(int i=1;i<=n;++i) a[i]=read();
	int tmp=0;
	for(int i=1;i<=n;++i) tmp=gcd(tmp,a[i]);
	if(tmp!=1){
		printf("%s\n","not coprime");
		return 0;
	}
	for(int i=1;i<=n;++i) nums[a[i]]++;
	bool flag=true;
	for(int i=2;i<=100010;++i){
		int sum=0;
		for(int j=i;j<=1000010;j+=i) sum+=nums[j];
		if(sum>1){
			flag=false;
			break;
		}
	}
	if(flag==true){
		printf("%s\n","pairwise coprime");
		return 0;
	}
	else{
		printf("%s\n","setwise coprime");
		return 0;
	}
}

C. 问答

往贪心里贪就好了

#include<bits/stdc++.h>
using namespace std;
int P=1000000009;
int fast(int x,int n){
	long long res=1,a=x;
	while(n){
		if(n&1)res=res*a%P;
		n>>=1;
		a=a*a%P;
	}
	return res;
}
int main(){
	int n,m,K;
	cin>>n>>m>>K;
	int t=(n/K)*(K-1)+n%K;
	if(t>=m)printf("%d\n",m);
	else{ 
		int p=m-t;//需要翻倍p次，都在前面翻倍 
		//(K*2+K)*2+K)*2...=K*(2^p+2^(p-1)+...+2) =K*2*(2^q-2)
		long long ans=K*2LL*(fast(2,p)-1)%P;
		int left=m-p*K;
		ans=(ans+left)%P;
		if(ans<0)ans+=P;
		cout<<ans<<endl;
	}
	return 0;
}

D. 发奖金

用二分去实现每个for循环的贪心就好了

int n, s;
#define MAX 1000005
struct node
{
    int l, r;
} a[MAX];
bool cmp(node A, node B)
{
    return A.l < B.l;
}

bool check(int x)
{
    vector<node> v;
    int l = 0, r = 0, sum = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i].r < x)
        {
            l++;
            sum += a[i].l;
            continue;
        }
        if (a[i].l > x)
        {
            r++;
            sum += a[i].l;
            continue;
        }
        v.push_back(a[i]);
    }
    if (l > n / 2) {
        return false;
    }
    for (int i = 0; i < n / 2 - l; i++)
    {
        sum += v[i].l;
    }
    for (int i = 1; i <= n / 2 + 1 - r; i++)
    {
        sum += x;
    }
    return sum <= s;
}

signed main()
{
    IOS;
    cin >> n >> s;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].l >> a[i].r;
    }
    sort(a + 1, a + 1 + n, cmp);
    int ans = 0;
    int l = a[n/2].l , r = s;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            l = mid + 1;
            ans = mid;
        }
        else
        {
            r = mid - 1;
        }
    }
    cout << ans << endl;

    return 0;
}

E. 逃出生天

如果把在同一地点的不同时间看作不同的状态，那么递推就是线性的

#define M 205
int n,m,tot,sx,sy,fx[]={1,-1,0,0,0,0,1,-1};
char mp[M][M];
double dp[M][M][M];
double dfs(int x,int y,int w){
	if(mp[x][y]=='E'||w==tot)return 0;
	if(dp[x][y][w]!=-1)return dp[x][y][w];
	int gd=0;
	double ans=0;
	for(int i=0;i<4;++i){
		int s=x+fx[i],t=y+fx[i+4];
		if(s<1||s>n||t<1||t>m||mp[s][t]=='#')continue;
		gd++;ans+=dfs(s,t,w+1);
	}
	if(gd!=0)ans=ans/gd+1;
	else ans=(tot-w);
	return dp[x][y][w]=ans;
}
int main(){
	scanf("%d%d%d%d%d",&n,&m,&tot,&sx,&sy);
	for(int i=1;i<=n;++i)scanf("%s",mp[i]+1);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
			for(int k=0;k<=tot;++k)dp[i][j][k]=-1;
	printf("%.6lf\n",dfs(sx,sy,0));
}

TEST 7

A. 老C的输入法

B. coprime

C. 问答

D. 发奖金

E. 逃出生天

F. 赛车