题目出难了，本来想祝大家寒假快乐的，现在只希望大家不要受题目的影响并从中有所收获吧😂。
寻找相似度（模拟）
计算出两个数的二进制形式1的个数并选择最小的个数为总匹配对数，从最小的数字的二进制最高位开始一一匹配，匹配过程中如果某个位置不为1则需要移动。（其实就是从最高可以匹配的位置开始把1尽量堆到前面）
#include<stdio.h>
int fun(int x,int a[],int *ans)//转换成二进制，储存1的个数并返回最高位数
{
int n = 0;
while(x)
{//x&1就是判断二进制最低位是否为1即是否是偶数
if(x&1)a[++n] = 1,(*ans)++;
else a[++n] = 0;
x>>= 1;// 右移一位， 就是x/=2;
}
return n;
}
int min(int x,int y)//返回最小值
{
if(x>y) return y;
else return x;
}
int main()
{
int t;
int a[100], b[100];
scanf("%d", &t);
while(t--)
{
int x, y;
int sum1 = 0, sum2 = 0, n1 = 0, n2 = 0, ans1 = 0, ans2 = 0;
//sum1记录交换次数，sum2记录相似度//n1,n2记录x,y二进制最高位数//ans1,ans2分别记录x，y 数字1的个数
scanf("%d%d", &x, &y);
n1 = fun(x, a, &ans1),n2 = fun(y, b, &ans2);
for (int i = min(n1, n2), j = min(ans1, ans2); i >= 1 && j >= 1; i--, j--)
{ //i从最高的有效位数开始，j从x，y最多有效匹配的对数开始
sum2 += i;//尽量让最高位匹配
if(a[i]==0) sum1++;
if(b[i]==0) sum1++;//如果为0则交换
}
printf("%d %d\n", sum1, sum2);
}
return 0;
}
勇士的末路（递推/动态规划）
去到某个房间的上一个房间只能由上方或左侧的房间进入，所以每个房间的最大金币数为 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + x，i,j分别为房间所在的行和列，x为当前房间金币数。
#include<stdio.h>
typedef long long int LL;
LL dp[1010][1010]={0};//明显会爆int所以开longlong
LL max(LL a,LL b)
{
if(a>b) return a;
else return b;
}
int main()
{
int n, m, w;
scanf("%d %d %d", &n, &m, &w);
for (int i = 1; i <= n;i++)
{
for (int j = 1; j <= m;j++)
{
int x;
scanf("%d", &x);
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + x;//状态转移方程
//每个房间的最大金币数只能由上或左的房间得到
}
}
if(w<n+m-1) printf("-1\n");//消耗能量固定为n+m-1
else printf("%lld\n", dp[n][m]);
return 0;
}
数字统计
只需要注意当秒数为0时0的个数为1，我特意提示判断边界但是很多同学还是掉坑里了。
#include<stdio.h>
int num[20];
int time(int y,int m,int d,int h,int t,int s)//计算并返回秒数
{
int a[20] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int ans=d-1;
if((y%4==0&&y%100!=0)||(y%400==0))a[2] = 29;//判断是否是闰年，二月要变化
for (int i = 1; i < m;i++)
ans += a[i];//总天数
ans = ans * 3600 * 24;
ans += (h * 3600 + t * 60 + s);
return ans;
}
int main()
{
int y, m, d, h, t, s,sum;
scanf("%d %d %d %d %d %d", &y, &m, &d, &h, &t, &s);
sum = time(y, m, d, h, t, s);
if(sum==0)num[0]=1;
while(sum)
{
num[sum % 10]++;
sum /= 10;
}
for (int i = 0; i <= 9;i++)
printf("%d ", num[i]);
return 0;
}
最大数（模拟、贪心）
首先输入的数据很大longlong显然会爆，之后发现虽然要求输入一个组合后的数但是本质其实是排序，所以重点是排序规则是关键。我们发现当两个数位数相同时从高位向低位比较发现某一位上的数字不相等则大的那个数放前面。发现两个数位数不同时则依然从高位开始比较如果有不同的数字处理同上，如果前面都相同则需要比较位数少的数的最高位和另一个数剩下的位数依然大的位数所在的数放前面。
#include<stdio.h>
#include<string.h>
char a[100][100];//由于数字很大所以选择用字符串储存
void swap(char x[],char y[])//字符串交换
{
char c[100];
strcpy(c, x), strcpy(x, y), strcpy(y, c);
}
int judge(char x[],char y[])
{
char x1[100], y1[100];//x1代表不交换的组合，y1代表交换的组合
strcpy(x1, x), strcpy(y1, y);//x,y复制到x1,y1
strcat(x1, y), strcat(y1, x);//构建x+y和y+x形式的字符串
return strcmp(x1, y1);//比较大小并返回，判断交换位置是否有利
}
void sort(int n)//选择排序
{
for (int i = 1; i <= n;i++)
for (int j = i+1; j <= n;j++)
if(judge(a[i],a[j])<0)
swap(a[i],a[j]);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n;i++)
scanf("%s", a[i]);
sort(n);//排序
for (int i = 1; i <= n;i++)
printf("%s", a[i]);//直接输出
return 0;
}
宝石（数学）
对每个宝石求约数，标记某个约数在数组中出现的次数，再从最大的约数向下遍历观察其数量是否满足组成项链的要求。
#include<stdio.h>
int num[1000010], sum[1000010];
void func(int x)//求每个数的约数
{
for (int i = 1; i <= x / i;i++)
if(x%i==0)
{
num[i]++;//标记每种约数的出现次数
if(x/i!=i)num[x / i]++;
}
}
int max(int x,int y)//返回最大值
{
if(x>y)return x;
else return y;
}
int main()
{
int n, maxn = 0, ans = 1, w = 0, res = 0;
scanf("%d", &n);
for (int i = 1; i <= n;i++)
{
int x;
scanf("%d", &x);
func(x);
maxn = max(x, maxn);//maxn记录最大数也就是最大的约数
}
for (int i = maxn; i >= 1 && ans <= n;)//i从maxn开始以满足每种项链的美丽值最大
{
if(num[i]>=ans)
{
sum[i]++;//sum记录对应约数(美丽值)的出现次数
if(sum[i]>res)
w = i, res = sum[i];//res记录次数的最大值，w记录对应的美丽值
ans++;//ans为你需要选择的宝石数，如果num[i]成功则组成的宝石数加一
}
else i--;//如果这个约数无法满足要求则遍历其他约数
}
printf("%d", w);
return 0;
}
打印图形（递归
每次由中心向四个角和中心递归直到阶数为1，3的阶数减1次方为“类X形”边长（数据不大也可以直接输出，其实这题本身就是让大家输出四种情况的，下面是进阶做法）。
#include<stdio.h>
#include <string.h>
char a[3000][3000], ch;
int xx[10] = {1, -1, 1, -1, 0}, yy[5] = {1, 1, -1, -1, 0};//方便递归“类X型”的5个方向
int func(int x)//计算3的x次方并返回
{
int ans = 1;
while(x--) ans *= 3;
return ans;
}
void dfs(int step,int x,int y)//step记录对应的边长为3的step次方，x,y为当前位置
{
if(step==1)//当step==1时达到递归终点，结束
{
a[x][y] = ch;//标记位置
return;
}
int m = func(step - 2);
for (int i = 0; i < 5;i++)
dfs(step - 1, x + xx[i] * m, y + yy[i] * m);//分别向四个角的下一级中心点和当前点递归
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
memset(a, '\0', sizeof(a));//每次把a重置
int n,m;
scanf(" %d %c", &n,&ch);//前面加一个空格吞回车
m = func(n - 1);//m为类X型的边长
dfs(n, m / 2 + 1, m / 2 + 1);//从中心点开始递归
for (int i = 1; i <= m;i++)
{
for (int j = 1; j <= m;j++)
if(a[i][j]!=ch) printf(" ");//无标记输出空格
else printf("%c",ch);
printf("\n");
}
}
return 0;
}
比较大小
签到题
#include<stdio.h>
int main()
{
char a, b;
scanf("%c %c", &a, &b);
if(a<'0'||a>'9'||b<'0'||b>'9')
printf("-1");
else
printf("%c", a < b ? a : b);
return 0;
}
握手（二分）
对每一个数a[i]二分查找对应的t-a[i]
#include<stdio.h>
typedef long long int LL;
int a[100005];
int num[1000005]={0};//num记录每个数字的出现次数
int func(int l,int r,int x)//二分答案，返回匹配的数量
{
int mid;
while(l<=r)
{
mid = l + r >> 1;//(l+r)/2
if(a[mid]==x) return num[x];//如果找到直接返回
else if(a[mid]>x) r =mid - 1;//太大缩小右边界
else l = mid + 1;//太小缩小左边界
}
return 0;
}
int main()
{
int t, n;
scanf("%d %d", &t, &n);
for (int i = 1; i <= n;i++)
scanf("%d", &a[i]),num[a[i]]++;
LL sum = 0;//会爆int
for (int i = 1; i <= n;i++)
{
num[a[i]]--;//每次剔除数字防止重复
int f = func(i + 1, n, t - a[i]);//检查x=t-a[i]的数量
sum += f;
}
printf("%lld", sum);
return 0;
}
京公网安备 11010502036488号