A-计数问题

#include<bits/stdc++.h>

using namespace std;

int main()

{

int n,x,b,c,t=0;

cin>>n>>x;//输入范围与要查的数字；

for(int i=1;i<=n;i++)//一到n进行循环；

{

b=i;//为了不改变i的值，就把i赋值给一个数；

while(b)//如果b不等于0，继续循环；

{

c=b%10;//求是否是x，是的话计数器加1；

b=b/10;//求下一个数字是否为x；

if(c==x) t++;//计数器加1；

}

}

cout<<t<<endl;//输出计数器的数字；

return 0;//结束

}

B-表达式求值

这道题的读入方式不需要很复杂，直接 scanf（“%d”）和 scanf（“%c”）就可以，不会出问题。

处理方式是每一次读入判断其上一个运算符，进行相应的处理，然后添加到sum中。

注意如果开int，有可能两个2^31-1相乘，可能出问题。所以都用long long存。

只输出后四位，则每一步操作都%10000即可。

#include <bits/stdc++.h>

using namespace std;

int main()

{

long long x, ans = 0, sum = 0; //记得ans初始值赋为0；sum为其中一段运算（即一段连续的乘积）的值

char last = 0, now; // last存储上一个运算符，now为新读入的运算符

bool flag = true; //控制循环的变量 后文有描述

while (flag)

{

scanf("%lld", &x);

// scanf有返回值 返回的是读入的字符数now

flag = scanf("%c", &now) == 1 ? true : false;

//如果没有运算符读入了，则flag=false，既保证了此次循环的正常运行，又能在下一遍循环跳出

if (last == 0) sum = x; //如果是刚开始读入，则直接赋值

if (last == '+')

{

ans = (ans + sum) % 10000;

sum = x;

//如果上一个操作是加法，则将前一段的值加入到ans中，然后再更新此新段的值

}

if (last == '*') sum = (sum * x) % 10000; //如果上一个运算是乘法，则将此数乘入本段的值中

if (!flag) ans = (ans + sum) % 10000; //如果是最后一个元素，则进行最后的更新

last = now; //将下一个读入的运算符作为新的一个循环的上一个运算符，并继续循环

}

printf("%lld", ans); //输出

return 0;

}

C-选数分组

注：这道题有点难度，应该放在第四题，此处有出题失误，如果看不懂题解不用强求。

首先，一共有20头奶牛，那么考虑对于每一头奶牛来说有3种状态，放在一组，放在另一组，不放任何一组，如果暴力枚举时间复杂度为O(3^n) > 1e9，无法接受。

考虑将n头奶牛分为两半，每组分别暴力求解，时间复杂度O(3^\frac{n}{2})可以通过。

假设在前一半中，在第一组中放的数的和为a，在第二组中放的数为b。

假设在后一半中，在第一组中放的数的和为c，在第二组中放的数为d。

我们需要第一组和第二组和相等，即a+c=b+d。

由于我们要对每一半分开处理，所以考虑将同一半的数放在一起处理，即移项得a-b=d-c。

因此，我们只需要统计在每一半中和为a-b 或 d-c的方案有多少种，再进行组合。

一个数被放入第一组中，a-b的值变大，在第二组中，a-b的值变小，如果不放，则a-b不变，所以维护a-b的值即可。

d-c同理，不管是c-d还是d-c本质上没有区别，处理方法与a-b相同。

但是这里要注意题中问的是： “给n个数，从中任意选出一些数，使这些数能分成和相等的两组。求有多少种选数的方案。” 也就是说，只要某一组数可以分成两个相等的集合，不管这一组可以有多少种方案分成两个相等的集合那么计数加一，而不是求所有的两个集合相等的组合方案数。

所以我们需要判重，这道题判重可以用状态压缩的思想。如果我们有十个数可以选，现在用于判重的是数字5，变为二进制是0000000101，就表示第一个和第三个被选了。代码中用到的位运算符号大家不了解的可以自行学习。

#include <bits/stdc++.h>

using namespace std;

int n, N, a[21], ans[2000001], s, tot;

vector<int> p[2000001];

map<int, int> b;

void dfs1(int x, int sum, int now)

{ //对前一半搜索，x表示到了第几个，sum表示a-b的值，now表示状压，取了那些数

if (x > N)

{

if (b[sum] == 0) b[sum] = ++tot; //如果a-b是第一次找到sum这个值 就用一个编号来表示sum

p[b[sum]].push_back(now); //将now这种方案放入以sum的编号b[sum]作为下标的vector数组中

return;

}

dfs1(x + 1, sum + a[x], now | (1 << (x - 1))); //三种情况讨论

dfs1(x + 1, sum - a[x], now | (1 << (x - 1)));

dfs1(x + 1, sum, now);

}

void dfs2(int x, int sum, int now)

{ //对后一半搜索，同上

if (x > n)

{

int t = b[sum]; //取出sum对应的编号

if (t != 0) //如果sum有编号 证明a-b出现过sum这个值 那就可以累计答案 如果t==0 就表示a-b没有这个值

for (int i = 0; i < p[t].size(); i++)

ans[p[t][i] | now] = 1; //对于每一种可能的组合，将值赋为1，意为这种方案取数可行

//注意，题目中要求的方案数为取数的方案数而不是分数的方案数，因此不是+1而是=1

return;

}

dfs2(x + 1, sum + a[x], now | (1 << (x - 1)));

dfs2(x + 1, sum - a[x], now | (1 << (x - 1)));

dfs2(x + 1, sum, now);

}

int main()

{

scanf("%d", &n);

N = n / 2;

for (int i = 1; i <= n; i++)

scanf("%d", &a[i]);

dfs1(1, 0, 0); //处理前一半

dfs2(N + 1, 0, 0); //处理后一半

for (int i = 1; i <= (1 << n); i++)

s += ans[i];

printf("%d", s);

return 0;

}

D-超能侠的魔法

这道题的主要难点在于旋转的代码怎么描述，剩余的就是模拟即可。如果一时不知道怎么写，可以多在纸上画一画旋转的情况，找到旋转前和旋转后坐标的对应关系。

不妨设旋转的中心(x,y)为原点(0,0)，这样在纸上模拟一下就可以得到顺时针旋转90°后正方形上一点(i,j)坐标变成(j,-i)，逆时针旋转90°后坐标变成(-j,i)。所以我们只需要枚举i,j即可，坐标需要加上偏移量x和y。

注意旋转时因为会覆盖其他数字，所以需要用一个新数组暂存旋转后的情况，代码中原数组为a，暂存数组为b。

#include <bits/stdc++.h>

using namespace std;

int n,m;

int x,y,r,z;

int a[510][510],b[510][510];

void change(int x,int y,int r,int z)

{

if(z==0)

{

for(int i=-r;i<=r;i++)

{

for(int j=-r;j<=r;j++)

{

b[x+j][y-i]=a[x+i][y+j];

}

}

}

if(z==1)

{

for(int i=-r;i<=r;i++)

{

for(int j=-r;j<=r;j++)

{

b[x-j][y+i]=a[x+i][y+j];

}

}

}

}

void same()

{

for(int i=1;i<=n;i++)

{

for(int j=1;j<=n;j++)

{

a[i][j]=b[i][j];

}

}

}

void print()

{

for(int i=1;i<=n;i++)

{

for(int j=1;j<=n;j++)

{

cout<<b[i][j]<<' ';

}

cout<<endl;

}

}

int main()

{

scanf("%d%d",&n,&m);

a[1][1]=1;

for(int i=1;i<=n;i++) //得到原数组 这一段大家可以自由发挥

{

if(i!=1) a[i][1]=a[i-1][1]+n;

for(int j=1;j<=n;j++)

{

if(j!=1) a[i][j]=a[i][j-1]+1;

b[i][j]=a[i][j];

}

}

for(int i=1;i<=m;i++)

{

scanf("%d%d%d%d",&x,&y,&r,&z);

change(x,y,r,z);

same(); //将改变后的数组复制到原数组中

}

print(); //输出答案

return 0;

}