A.棋盘

这是弱化了无数次的版本。。。

• 每个$?$的值等于其横行$*$的数量加纵列$*$的数量。
• 发现每一行$?$要统计的行中$*$的数量和这一行中的其他$?$一样；列也同理。
• 我们遍历统计每行每列有多少$*$，输出时将$?$所在的行列$*$数相加即可得到答案。复杂度为$O(n*m)$， 总体要$10^4$次运算左右，评测机性能每秒运算次数在$10^8$左右,可以接受。
• 如果遍历每个$?$都求一遍横行$*$的数量和纵列$*$的数量，复杂度为$O(n^3)$,总体要$10^6$次运算，评测机性能每秒运算次数在$10^8$左右，也可以接受。

//c
#include<stdio.h>
int n,m;
int main()
{
    scanf("%d%d",&n,&m);
    char s[n+10][m+10];
    int  b[n+10]={0},c[m+10]={0};//用来存储每行有多少，每列有多少； 
    for(int i=0;i<n;i++){
    	 scanf("%s",&s[i]);
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(s[i][j]=='*'){
				b[i]++;
				c[j]++; 
			}//统计每行有多少，每列有多少；
		}
    }
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(s[i][j]=='*'){
				printf("*");
			}
			else{
				printf("%d",b[i]+c[j]);
			}
		}
		printf("\n");
	}
    return 0;
}

B.上帝做我的见证(Aster_Blythe)

思路：签到题，利用\n换行输出即可，也可以用\作为换行标识符来在编译器内换行以便于阅读：

#include<stdio.h>

int main() {
	printf("上帝做我的见证\n\
见证我不会被任何事情打垮\n\
等这一切都结束后\n\
我永远不再挨饿 不让家里人挨饿\n\
哪怕说谎 去偷去骗去杀人\n\
上帝做我的见证\n\
我决不再挨饿");
	
	return 0;
} 

C.天干地支

• 天干和地支各自独立循环选用，所以我们用$\%$取模来实现其循环（取模就是求余数）。
  
• 我们对$2025$模$10$得下标$5$（下标从$0$开始），对应"ji"，但其实际为"yi"。所以求天干$n$应减$4$后再取模；
  同理，对$2025$模$12$得下标$9$（下标从$0$开始），对应"you"，其实际为"si"。所以求地支$n$应减$4$后再取模；（不必担心负数取模会出错）

//c
#include<stdio.h>
int n;
char t[10][5] = {"jia", "yi", "bing", "ding", "wu", "ji", "geng", "xin", "ren", "gui"};
char d[12][5] = {"zi", "chou", "yin", "mao", "chen", "si", "wu", "wei", "shen", "you", "xu", "hai"};

int main()
{
    scanf("%d",&n);
    printf("%s%s\n", t[(n-4)% 10], d[(n-4)% 12]);
    return 0;
}

c++的string处理字符串更方便，这里直接调整天干地支的顺序，与上述$(n-4)$的效果一样。

//c++
#include <iostream>
using namespace std;
int n;
string t[10] = {"geng", "xin", "ren", "gui", "jia", "yi", "bing", "ding", "wu", "ji"};
string d[12] = {"shen", "you", "xu", "hai", "zi", "chou", "yin", "mao", "chen", "si", "wu", "wei"};
int main()
{
    cin >> n;
    cout << t[n % 10] << d[n % 12] << endl;
    return 0;
}

D.二元一次函数值排序

• $A，B，C$都大于$0$，$x$还被限制为正整数，那么显然函数都是单调递增的。观察发现$n,m$的值给的都不大，我们不妨枚举出每个函数的前$m$个函数值，将他们放在一起从小到大排序，再取前$m$个自是所求。
• 要枚举的函数值时间复杂度为$On*m$,小于$10^4$次运算。排序有多种方法，我们就用最基本的冒泡排序，时间复杂度为$O(n*m)^2$,需要$10^8$次运算。总体要$10^8$次运算，评测机性能每秒运算次数在$10^8$左右，实测可过。
• 冒泡排序:遍历数组，若一个数小于它前面的数就交换他们的位置。重复进行，数组有序性增加，这样最多遍历$n*m-1$次，数组就会严格递增。

  //c
#include<stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int n,m,A,B,C;
int main()
{
    scanf("%d%d",&n,&m);
    int t=n;
    int a[n*m+10];
    while(t--){
    	scanf("%d%d%d",&A,&B,&C);
    	for(int i=1;i<=m;i++){
    		a[t*m+i]=A*i*i+B*i+C;
		} 
	}
	t=n*m;
	while(t--){
		for(int i=2;i<=n*m;i++){
    		if(a[i]<a[i-1]){
    			swap(&a[i],&a[i-1]);//若前面的数大于后面的数swap其值。
			}
		}
	}
	for(int i=1;i<=m;i++){
		printf("%d ",a[i]);
	}
    return 0;
}

E.天呐，一只树苗鼹鼠！（Aster_Blythe）

思路：直接复制样例进行修改，利用\作为换行标识符更便于阅读 注意点： 1、字符数组对于开心/死亡的修改与输出 2、血量输出判断逻辑为“每损失10点生命值减少一格” 3、用“─”符号填充损失的生命值格数 4、血量数字位置共三格，若血量减少为两位或一位数时，要补充空格 5、血量最低为0

#include<stdio.h>
#include<string.h>

int main() {
	int n, m, hp = 100, g;
	char zt[] = "开心";
	scanf("%d%d", &n, &m);
	hp -= n * m;
	if(hp <= 0) {
		strcpy(zt, "死亡"); //来自c标准库<string.h> 
		hp = 0;
	}
	g = n * m / 10;
	if(g > 10) g = 10;
	// cout << g;
	printf("\
╔══════════════════════════════════╗\n\
║        ★★★ 树苗鼹鼠 ★★★      ║\n\
╠══════════════════════════════════╣\n\
║      ★ 当前状态：[ %s ] ★      ║\n\
╠══════════════════════════════════╣\n\
║``````````?????`````?????`````````║\n\
║``````````?.....?*?....?``````````║\n\
║````````````?........??```````````║\n\
║```````````````??.?```````````````║\n\
║```````````````??.?```````````````║\n\
║`````````````???..?```````````````║\n\
║``````````????.....???````````````║\n\
║```````????...........???`````````║\n\
║`````????................??```````║\n\
║````???..Q..........Q.  ...?``````║\n\
║```???.......╚══╝...........?`````║\n\
║```????....................?``````║\n\
║`````?????................??``````║\n\
║```??.....??.??????.........??````║\n\
║````?........?```````?........?```║\n\
╠══════════════════════════════════╣\n\
║    HP: [", zt);
    for(int i = 0; i < 10 - g; i++) {
    	printf("█");
    }
    for(int i = 0; i < g; i++) {
    	printf("─");
    }
    printf("]  ");
    if(hp < 10) {
    	printf("  %d/100     ║\n", hp);
    }
    else if(hp < 100) {
    	printf(" %d/100     ║\n", hp);
    }
    else {
    	printf("%d/100     ║\n", hp); //hp==100
    }
    printf("╚══════════════════════════════════╝\n");
	
	return 0;
}

F.呼老魔的一击

• 由于有负数的存在，对序列直接求和显然是不理智的。
• 若暴力求出所有的子段的和，我们会发现仅子段的数量就有$n^2$的时间复杂度（任选两个边界做子段有$C\binom{2}{n}$种组合）。以题目中$n$的限制条件，评测机要运算超过$10^9$次，而一般评测机性能每秒运算次数在$10^8$左右，显然超时TLE。
• 我们可以贪心点，假设子段都要取到序列的末尾，让你从某处砍头不要前面的了，你会选择从哪砍？
• 若第一个数是负数，那肯定不会要它。若为正数，那可以暂时保留。我们可以从前往后不断统计每个数与它前面所有的数之和，若为和负数，则从这开始砍是赚的。那么最赚的肯定是前缀和负的最狠的，因为减去一个负数得到一个正数。（若最小的前缀和仍为正数，则不砍全要）
• 序列$\{2,-3,5,-7,1\}$的前缀和$\{2,-1,4,-3,-2\}$；
• 怎样求前缀和？对每个数都从头计算它与它前面所有的数之和显然是不聪明的。我们发现每个数的前缀和等于它自身加上它前一个数的前缀和，可由此递推出序列中所有数的前缀和，最后一个数的前缀和显然就是序列之和。
• 这样我们就能求出子段取到序列的末尾的最优解，但是末尾并不一定是本题的最优解。从前往后枚举每一个数充当末尾，用一个变量来维护它前面的前缀和最小值（枚举到前缀和小于变量，则更新变量），每枚举到一个数就用它的前缀和减去它前面的其他数的前缀和的最小值（小于$0$就减了），若大于答案ans就更新答案。
• 每个数求前缀和的复杂为$On$,枚举复杂度也为$On$。所以运算次数不会超过$10^6$。

//c
#include<stdio.h>
inline int min(int x, int y) {
return (x < y) ? x : y;
}
inline int max(int x, int y) {
return (x > y) ? x : y;
}
int n,x,ans=0;
int main()
{
    scanf("%d",&n);
    int a[n+10];
    int b[n+10];//b用来存前缀和； 
    for(int i=1;i<=n;i++){
    	scanf("%d",&a[i]);
	}
	b[1]=a[1];
	for(int i=2;i<=n;i++){
		b[i]=b[i-1]+a[i]; 
	}
	ans=b[1];
	x=min(b[1],0);//x用来存前缀和的最小值 ,x不能大于0； 
	for(int i=2;i<=n;i++){
		ans=max(ans,b[i]-x);
		x=min(x,b[i]); 
	}
	printf("%d\n",ans);
    return 0;
}

• 下面提供另一个复杂度为$O(n)$的解决思路。
• 如上所言，一个区间必然以数组中的某个下标为结尾，我们只要枚举每个结尾的最优解，更新最大值ans即可。
• 从a[0],开始以a[0]为结尾的最大子段显然只有a[0]本身。我们往后推进发现，以某个下标为结束的最大值段，要么是它连接上上一个下标结尾的最大值段，要么是以它自身为开头的子段（如果以它上一个下标为结尾的最大子段和为负数，显然不如以自己为开头，重新开始）。
• 就这样遍历数组，不断维护着以某个下标为结尾的最大值x，和整体的最大值ans,遍历完数组即求解出答案。

//c++
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin>>n;
	int ans,x;
	vector<int>a(n+10);//vector就是数组;
	for(int i=0;i<n;i++){
		cin>>a[i];//cin就是scanf输入;
	}
	ans=a[0];x=a[0];
	for(int i=1;i<n;i++){
		x=max(x+a[i],a[i]);
		ans=max(x,ans); 
	}
	cout<<ans<<endl;//cout就是printf输出;
}

G.月饼奖励

• 无论怎样，所有的月饼都会被吃完。
• 浦月吃最小的组，彗星吃中间的组，所以每次无论怎样分组，浦月都不可能比彗星吃的多。 那么理想情况的分组应让前两组一样多，这样每次浦月都能和彗星吃一样多的。
• 这带来一个问题，被吃的月饼永远是偶数，即剩余的月饼奇偶性不会变。
  那么若初始$n$为偶数，最后会余下$2$块被彗星直接吃，彗星比浦月多吃$2$；
  若初始$n$为奇数，最后会余下$1$块被彗星直接吃，彗星比浦月多吃$1$。
• 无论怎样浦月至少比彗星少吃一块，所以浦月吃的块数$\left\lfloor\dfrac{n-1}{2}\right\rfloor$向下取整。

//c
#include<stdio.h>
int t,n;
int main()
{
    scanf("%d",&t);
    while(t--){
    	scanf("%d",&n);
    	printf("%d\n",(n-1)/2);
	}
    return 0;
}

H.无尽能源

• 用$(x,y)$记录下当前坐标，遍历字符串，$\{L,R,D,U\}$分别对应$\{x-1,x+1,y-1,y+1\}$。每次更新$(x,y)$，若$(x,y)$为$(1,1)$则输出"YES"flag标记为$0$退出循环，遍历完后仍未输出"YES"则输出"NO"。
• 字符串跟数组差不多，都能下标访问。

  //c
#include<stdio.h>
int t,n,x,y;
bool flag;
int main()
{
	scanf("%d",&t);
	while(t--){
		x=0;y=0;
		flag=1;
		scanf("%d",&n);
        char s[n+10];
        scanf("%s",&s);
        for(int i=0;i<n;i++){        	
    	    if (s[i] == 'L') x--;
		    if (s[i] == 'R') x++;
		    if (s[i] == 'D') y--;
		    if (s[i] == 'U') y++;
		    if (x == 1 && y == 1){
		    printf("YES\n");
		    flag=0;
		    break;
		    }
	    }
	    if(flag){
		    printf("NO\n");
	    }
	}
    return 0;
}