4月11日省赛，给自己加油！
矩阵翻硬币：给定n,m。这么大的数据很明显找规律。。。。打表处理小数据，代码：
int a[500][500];
int main(){
int n,m,ans;
int i,j,k,l;
while(scanf("%d%d",&n,&m)!=EOF){
memset(a,0,sizeof(a));
ans=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
for(k=1;k<=n;k++)
for(l=1;l<=m;l++)
if (k%i==0&&l%j==0)
a[k][l]^=1;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
if (a[i][j]) ans++;
printf("%d ",a[i][j]);
}
puts("");
}
printf("%d\n\n",ans);
}
return 0;
}发现只有平方数的地方不一样。。那么假设n中有a个平方数，m中有b个，答案就是a*b。直接上大数模版即可！或者用Java。。。
兰顿蚂蚁：模拟。看懂题目跟着做就好了。注意，题中已经规定好坐标从(0,0)开始算，对有Pascal习惯的童鞋。。。看清楚题目！
实现的小技巧：按照顺序（逆时针或者顺时针的方向）排列上下左右，在处理转弯的时候特别方便。上代码：
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
//方向为上，右，下，左
int map[200][200];
int main(){
int i,j;
char s[5];
scanf("%d%d",&m,&n);
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf("%d",&map[i][j]);
scanf("%d%d%s%d",&x,&y,s,&k);
int dir;
if (s[0]=='U') dir=0;//初始的方向定好
else if (s[0]=='D') dir=2;
else if (s[0]=='L') dir=3;
else dir=1;
while(k--){
if (map[x][y]){//右转
map[x][y]=1-map[x][y];
dir=(dir+1)%4;
x+=dx[dir];
y+=dy[dir];
}
else{//白格，左转90
map[x][y]=1-map[x][y];
dir=(dir-1+4)%4;
x+=dx[dir];
y+=dy[dir];
}
}
printf("%d %d\n",x,y);
return 0;
}
分糖果：模拟啊。。。不知道多少次，那么判断一次如果不满足条件继续执行就好了
int a[maxn],b[maxn];
int ans,n;
void solve(){
int i;
for(i=0;i<n;i++){
b[(i+n-1)%n]=a[i]/2;
a[i]/=2;
}
for(i=0;i<n;i++){
a[i]+=b[i];
b[i]=0;
if (a[i]%2){
a[i]++;
ans++;
}
}
}
int main(){
int i,j,k;
while(scanf("%d",&n)!=EOF){
for(i=0;i<n;i++) scanf("%d",&a[i]);
ans=0;
while(1){
int flag=0;
for(i=1;i<n;i++)
if (a[i]!=a[0]){
flag=1;
break;
}
if (flag) solve();
else break;
}
printf("%d\n",ans);
}
return 0;
}
数字游戏：模拟题。注意数学符号%的使用，不需要真正按照循环报数去找，每次间隔的数有规律的，找到规律直接输出
num是每次报的数，看着式子肯定可以找到规律（从等差来想）
long long n,m,t,add,first,final,i,j,k,num,ans;
int main(){
//freopen("input.txt","r",stdin);
scanf("%I64d%I64d%I64d",&n,&k,&t);
ans=num=1;
for(i=0;i<t-1;i++){
first=i*n+1;
final=i*n+n;
add=(first+final)*n/2;
add=add%k;
num=(num+add)%k;
ans+=num;
}
printf("%I64d\n",ans);
}
回文数字：暴力算呗
const int maxn=1000050;
int ans[maxn],tot=0;
int main(){
int i,j,k,n;
scanf("%d",&n);
for(i=1;i<=9;i++)
for(j=0;j<=9;j++)
for(k=0;k<=9;k++){
if (2*i+2*j+k==n) ans[++tot]=i+j*10+k*100+j*1000+i*10000;
if (2*i+2*j+2*k==n) ans[++tot]=i+j*10+k*100+k*1000+j*10000+i*100000;
}
sort(ans+1,ans+1+tot);
for(i=1;i<=tot;i++)
printf("%d\n",ans[i]);
if (tot==0) puts("-1");
return 0;
}
买不到的数目：这道题是个数论结论题：答案为n*m-n-m
可以证明从n*m-n-m+1到无穷大的整数都可以用a*n+b*m表示
或者不知道结论就打表啊！！什么时候可以表示的数连续了，找到那个连续的数开始的位置，-1，就是答案。n和m都不大，是可以试试的。
连号区间数：不知道跟并查集有半毛钱关系。。。或者是我笨。。。
还是找的数学规律
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d",&num[i]);
for(i=1;i<=n;i++){
int minnum=num[i];
int maxnum=num[i];
for(j=i;j<=n;j++){
minnum=min(num[j],minnum);
maxnum=max(num[j],maxnum);
if (maxnum-minnum==j-i) ans++;
//如果满足这个条件说明！！
}
}
printf("%d\n",ans);
return 0;
}
翻硬币：觉得算不上，贪心！就是从左到右循环一次来更改一次，直到目标状态
const int maxn=2000;
char s1[maxn],s2[maxn];
int a[maxn],b[maxn],ans;
int main(){
//freopen("input.txt","r",stdin);
scanf("%s%s",s1,s2);
ans=0;
int len=strlen(s1),i,j,k;
for(i=0;i<len;i++){
if (s1[i]=='o') a[i]=0;
else a[i]=1;
if (s2[i]=='o') b[i]=0;
else b[i]=1;
}
for(i=0;i<len;i++){
if (a[i]!=b[i]){
ans++;
a[i]=1-a[i];
a[i+1]=1-a[i+1];
}
}
printf("%d\n",ans);
return 0;
}
错误票据：这种题用map做好了啊，基础map使用，注意：如果重复的和连续的出现在一起啦。。细节条件判断
const int maxn=500;
int a[maxn];
map<int,int>mp;
int ans1,ans2,n,num,i,j,k,tot;
int main(){
//freopen("input.txt","r",stdin);
scanf("%d",&n);
mp.clear();
tot=0;
while(scanf("%d",&num)!=EOF){
a[tot++]=num;
mp[a[tot-1]]++;
}
sort(a,a+tot);
for(i=0;i<tot;i++)
if (mp[a[i]]==2){
ans2=a[i];
break;
}
for(i=0;i<tot;i++)
if (a[i]+1!=a[i+1]&&mp[a[i]]==1){
ans1=a[i]+1;
break;
}
printf("%d %d\n",ans1,ans2);
return 0;
}带分数：最最自豪的一道题，感觉自己的代码无敌！
首先，此题肯定是个暴力题，怎么暴力。。。是个问题
N=A+B*C，表示成这样如果直接模拟算A，B，C，然后判重，然后判等，当然可以做，不过按照ACM的想法，考虑最大数据1000000不可能1s出解
注意，1-9的全排列可以完全表示出A，B和C
所以只需要表示出A，B和C。
Step1：生成1到9的全排列
Step2：将全排列的数组生成A和B和C
Step3：判等
代码如下：
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 99999999
#define pi 3.1415926535897932384626433832795028841971
int num[10],vis[10],n,ans=0;
void check(){
int i,j,a,b,c,num1,num2,num3;
for(i=1;i<=9;i++)
for(j=i+1;j<=9;j++){
num1=num2=num3=0;
for(a=1;a<=i;a++) num1=num1*10+num[a];
for(b=i+1;b<j;b++) num2=num2*10+num[b];
for(c=j;c<=9;c++) num3=num3*10+num[c];
if (num1+num2/num3==n&&num2%num3==0){
ans++;
//printf("%d %d %d\n",num1,num2,num3);
}
}
}
void dfs(int p){
if (p==10){
//for(int i=1;i<=9;i++) printf("%d%c",num[i],i==9?'\n':' ');
check();
return;
}
for(int i=1;i<=9;i++)
if (!vis[i]){
vis[i]=1;
num[p]=i;
dfs(p+1);
vis[i]=0;
}
return;
}
int main(){
int i,j,k;
scanf("%d",&n);
memset(vis,0,sizeof(vis));
dfs(1);
printf("%d\n",ans);
return 0;
}
由此方法，可以进一步得出打表的代码，如下：
注意判断范围在1000000以内！
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <stack>
using namespace std;
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 99999999
#define pi 3.1415926535897932384626433832795028841971
int num[10],vis[10],n;
int ans[1000050];
void check(){
int i,j,a,b,c,num1,num2,num3;
for(i=1;i<=9;i++)
for(j=i+1;j<=9;j++){
num1=num2=num3=0;
for(a=1;a<=i;a++) num1=num1*10+num[a];
for(b=i+1;b<=j-1;b++) num2=num2*10+num[b];
for(c=j;c<=9;c++) num3=num3*10+num[c];
if (num2%num3==0&&num1+num2/num3<=1000000) ans[num1+num2/num3]++;
}
}
void dfs(int p){
if (p==10){
//for(int i=1;i<=9;i++) printf("%d%c",num[i],i==9?'\n':' ');
check();
return;
}
for(int i=1;i<=9;i++)
if (!vis[i]){
vis[i]=1;
num[p]=i;
dfs(p+1);
vis[i]=0;
}
return;
}
int main(){
freopen("output.txt","w",stdout);
int i,j,k;
memset(vis,0,sizeof(vis));
memset(ans,0,sizeof(ans));
dfs(1);
for(i=1;i<=1000000;i++){
printf("%d,",ans[i]);
if (i%80==0) puts("");
}
//fclose(stdout);
//scanf("%d",&n);
//printf("%d\n",ans[n]);
return 0;
}
京公网安备 11010502036488号