本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
文章推荐
蓝桥杯练习系统习题-历年真题解析2
题目搜索方式：Ctrl+F—-> 输入题目名称—>定位到解答.
入门训练
基础练习
基础练习
算法训练
算法训练
算法训练
算法训练
算法训练
算法训练
算法提高
算法提高
历届试题
历届试题
基础练习
算法训练
算法训练
算法训练
算法提高
历届试题
历届试题 车轮轴迹
问题描述 栋栋每天骑自行车回家需要经过一条狭长的林荫道。道路由于年久失修，变得非常不平整。虽然栋栋每次都很颠簸，但他仍把骑车经过林荫道当成一种乐趣。 由于颠簸，栋栋骑车回家的路径是一条上下起伏的曲线，栋栋想知道，他回家的这条曲线的长度究竟是多长呢？更准确的，栋栋想知道从林荫道的起点到林荫道的终点，他的车前轮的轴（圆心）经过的路径的长度。 栋栋对路面进行了测量。他把道路简化成一条条长短不等的直线段，这些直线段首尾相连，且位于同一平面内。并在该平面内建立了一个直角坐标系，把所有线段的端点坐标都计算好。 假设栋栋的自行车在行进的过程中前轮一直是贴着路面前进的。
图片请百度
上图给出了一个简单的路面的例子，其中蓝色实线为路面，红色虚线为车轮轴经过的路径。在这个例子中，栋栋的前轮轴从A点出发，水平走到B点，然后绕着地面的F点到C点（绕出一个圆弧），再沿直线下坡到D点，最后水平走到E点，在这个图中地面的坐标依次为：(0, 0), (2, 0), (4, -1), (6, -1)，前轮半径为1.50，前轮轴前进的距离依次为： AB=2.0000；弧长BC=0.6955；CD=1.8820；DE=1.6459。 总长度为6.2233。
下图给出了一个较为复杂的路面的例子，在这个例子中，车轮在第一个下坡还没下完时（D点）就开始上坡了，之后在坡的顶点要从E绕一个较大的圆弧到F点。这个图中前轮的半径为1，每一段的长度依次为： AB=3.0000；弧长BC=0.9828；CD=1.1913；DE=2.6848；弧长EF=2.6224； FG=2.4415；GH=2.2792。 总长度为15.2021。
图片请百度
现在给出了车轮的半径和路面的描述，请求出车轮轴轨迹的总长度。 输入格式 输入的第一行包含一个整数n和一个实数r，用一个空格分隔，表示描述路面的坐标点数和车轮的半径。 接下来n行，每个包含两个实数，其中第i行的两个实数x[i], y[i]表示描述路面的第i个点的坐标。 路面定义为所有路面坐标点顺次连接起来的折线。给定的路面的一定满足以下性质：
*第一个坐标点一定是(0, 0)； *第一个点和第二个点的纵坐标相同； *倒数第一个点和倒数第二个点的纵坐标相同； *第一个点和第二个点的距离不少于车轮半径； *倒数第一个点和倒数第二个点的的距离不少于车轮半径； *后一个坐标点的横坐标大于前一个坐标点的横坐标，即对于所有的i，x[i+1]>x[i]。 输出格式 输出一个实数，四舍五入保留两个小数，表示车轮轴经过的总长度。 你的结果必须和参考答案一模一样才能得分。数据保证答案精确值的小数点后第三位不是4或5。 样例输入 4 1.50 0.00 0.00 2.00 0.00 4.00 -1.00 6.00 -1.00 样例输出 6.22 样例说明 这个样例对应第一个图。 样例输入 6 1.00 0.00 0.00 3.00 0.00 5.00 -3.00 6.00 2.00 7.00 -1.00 10.00 -1.00 样例输出 15.20 样例说明 这个样例对应第二个图 数据规模和约定 对于20%的数据，n=4； 对于40%的数据，n≤10； 对于100%的数据，4≤n≤100，0.5≤r≤20.0，x[i] ≤2000.0，-2000.0≤y[i] ≤2000.0。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 10000;
const double PI = atan(1.0) * 4;
const double EPS = 1e-10;
class Point {<!-- -->
public:
double x, y;
Point() {}
Point(double x, double y) : x(x), y(y) {}
Point operator - (const Point &r) const { return Point(x-r.x, y-r.y); }
Point operator + (const Point &r) const { return Point(x+r.x, y+r.y); }
Point &operator += (const Point &r) { x += r.x; y += r.y; return *this; }
Point &operator *= (double m) { x *= m; y *= m; return *this; }
Point pOfRotate(double angle) const {
double cosA = cos(angle);
double sinA = sin(angle);
return Point(cosA*x-sinA*y, sinA*x+cosA*y);
}
Point pOfRotate90() const { return Point(-y, x); }
double length() const { return sqrt(x*x+y*y); }
Point pOfNormal() const {
double len = length();
return Point(x/len, y/len);
}
double angle() const { return atan2(y, x); }
};
ostream & operator <<(ostream &os, const Point &v)
{
os << "(" << v.x << "," << v.y << ")";
return os;
}
class Segment;
class Circle;
class Seg {<!-- -->
public:
virtual double getLeft() const = 0;
virtual double getRight() const = 0;
virtual double getY(double x) const = 0;
virtual double getLength(double x1, double x2) const = 0;
virtual void intersect(Seg *r) const = 0;
virtual void intersect(const Segment &v) const = 0;
virtual void intersect(const Circle &v) const = 0;
bool contains(double x) const { return x>=getLeft() && x<=getRight(); }
virtual void acceptPrint(ostream &os) const = 0;
};
ostream & operator <<(ostream &os, const Seg &v)
{
v.acceptPrint(os);
return os;
}
Point intersectRet[4];
int tIntersectRet;
class Segment : public Seg {
public:
Point a, b;
Segment &moveLeft(double dis)
{
Point tmp = ((b-a).pOfRotate90().pOfNormal() *= dis);
a += tmp;
b += tmp;
return *this;
}
virtual double getLeft() const { return a.x; }
virtual double getRight() const { return b.x; }
virtual double getY(double x) const {
return (x-a.x)*(b.y-a.y)/(b.x-a.x)+a.y;
}
virtual double getLength(double x1, double x2) const {
return (x2-x1) * (b-a).length() / (b.x-a.x);
}
virtual void intersect(Seg *r) const {
r->intersect(*this);
}
virtual void intersect(const Segment &v) const {
tIntersectRet = 0;
double ang = (b-a).angle();
Point c = (v.a-a).pOfRotate(-ang);
Point d = (v.b-a).pOfRotate(-ang);
// Bug
//double di = b.length();
double di = (b-a).length();
if (!((c.y>0&&d.y<0) || (c.y<0&&d.y>0)))
return ;
double x = (d.x-c.x) * (-c.y) / (d.y-c.y) + c.x;
if (x<0 || x>di)
return ;
Point ret = Point(x,0).pOfRotate(ang)+a;
intersectRet[tIntersectRet++] = ret;
}
virtual void intersect(const Circle &v) const;
virtual void acceptPrint(ostream &os) const {
os << a << "-" << b;
}
};
class Circle : public Seg {
public:
Point c;
double r;
virtual double getLeft() const { return c.x - r; }
virtual double getRight() const { return c.x + r; }
virtual double getY(double x) const {
double y2 = r * r - (c.x - x) * (c.x - x);
if (y2<0) y2 = 0;
return c.y + sqrt(y2);
}
virtual double getLength(double x1, double x2) const {
x1 -= c.x; x2 -= c.x;
double a1 = Point(x1, sqrt(abs(r*r-x1*x1))).angle(), a2 = Point(x2, sqrt(abs(r*r-x2*x2))).angle();
return (a1-a2) * r;
}
virtual void intersect(Seg *r) const {
r->intersect(*this);
}
virtual void intersect(const Segment &v) const {
tIntersectRet = 0;
Point a = v.a - c;
Point b = v.b - c;
double ang = (b-a).angle();
Point nA = a.pOfRotate(-ang);
Point nB = b.pOfRotate(-ang);
double y = nA.y;
if (y>r || y<-r)
return ;
double x = sqrt(r*r - y*y);
if (x>=nA.x && x<=nB.x)
intersectRet[tIntersectRet++] = Point(x, y).pOfRotate(ang) + c;
if (-x>=nA.x && -x<=nB.x)
intersectRet[tIntersectRet++] = Point(-x, y).pOfRotate(ang) + c;
}
virtual void intersect(const Circle &v) const {
tIntersectRet = 0;
Point p = v.c - c;
double d = p.length();
if (d > r + v.r || d==0)
return ;
double x = (r*r - v.r*v.r + d*d) / (2*d);
if (x <= r)
{
double y = sqrt(abs(r*r - x*x));
double ang = p.angle();
intersectRet[tIntersectRet++] = Point(x,y).pOfRotate(ang) + c;
intersectRet[tIntersectRet++] = Point(x,-y).pOfRotate(ang) + c;
}
}
virtual void acceptPrint(ostream &os) const {
os << c << "," << r;
}
};
void Segment::intersect(const Circle &v) const {
v.intersect(*this);
}
int n;
Point inps[MAXN];
vector<Seg *> segs;
vector<double> spes;
double radius = 1;
void input()
{
scanf("%d%lf", &n, &radius);
for (int i = 0; i < n; ++i)
{
double x, y;
scanf("%lf%lf", &x, &y);
inps[i] = Point(x, y);
}
}
void process()
{
segs.clear();
spes.clear();
for (int i = 1; i + 1 < n; ++i)
{
Circle *tmp = new Circle;
tmp->c = inps[i];
tmp->r = radius;
segs.push_back(tmp);
}
for (int i = 0; i + 1 < n; ++i)
{
Segment *tmp = new Segment;
tmp->a = inps[i];
tmp->b = inps[i+1];
tmp->moveLeft(radius);
segs.push_back(tmp);
}
for (int i = 0; i < (int)segs.size(); ++i)
{
spes.push_back(segs[i]->getLeft());
spes.push_back(segs[i]->getRight());
}
for (int i = 0; i < (int)segs.size(); ++i)
{
for (int j = i+1; j < (int)segs.size(); ++j)
{
segs[i]->intersect(segs[j]);
if (tIntersectRet > 0)
{
for (int id = 0; id < tIntersectRet; ++id)
{
//cout << *segs[i] << " " << *segs[j] << " : " << intersectRet[id] << endl;
spes.push_back(intersectRet[id].x);
}
}
}
}
sort(spes.begin(), spes.end());
double pre = spes[0];
const double NONE = 1e30;
double preEnd = NONE;
double totalLen = 0;
for (int i = 1; i < (int)spes.size(); ++i)
{
if (spes[i]-pre < EPS)
continue;
double cur = (pre+spes[i]) / 2;
//cout << "Processing " << cur << " from " << pre << " to " << spes[i] << endl;
if (cur>=inps[0].x && cur<=inps[n-1].x)
{
double MY = -NONE;
int who;
for (int j = 0; j < (int)segs.size(); ++j)
{
if (!segs[j]->contains(cur))
continue;
double y = segs[j]->getY(cur);
if (y > MY)
{
MY = y;
who = j;
}
}
if (preEnd != NONE)
{
double LY = segs[who]->getY(pre);
//cout << "Drop info " << *segs[who] << " " << "[" << pre << "]" << endl;
totalLen += abs(preEnd-LY);
//cout << "Pre drop = " << abs(preEnd-LY) << " from " << preEnd << " to " << LY << endl;
}
double len = segs[who]->getLength(pre, spes[i]);
if (len < 0)
printf("Error!\n");
//cout << "Curlen = " << len << " from " << pre << " to " << spes[i] << endl;
totalLen += len;
preEnd = segs[who]->getY(spes[i]);
}
pre = spes[i];
}
printf("%0.2lf\n", totalLen);
for (int i = 0; i < (int)segs.size(); ++i)
delete segs[i];
segs.clear();
}
int main()
{
input();
process();
return 0;
}
历届试题 九宫重排
问题描述 如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。
图为2个9宫格，第一个为123,456,78空格。第二个为123，空格46,758。
我们把第一个图的局面记为：12345678. 把第二个图的局面记为：123.46758 显然是按从上到下，从左到右的顺序记录数字，空格记为句点。 本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。 输入格式 输入第一行包含九宫的初态，第二行包含九宫的终态。 输出格式 输出最少的步数，如果不存在方案，则输出-1。 样例输入
- 123.46758 样例输出 3 样例输入
-
- 1. 样例输出 22
```
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct _Node
{
char tab[3][3];
int x,y;
int no;
}Node,*pNode;
int vx[4]={-1,1,0,0};
int vy[4]={0,0,-1,1};
Node res[400000];
int front=0,rear=0;
int vis[4000000],fact[9];
void input(pNode start);
void bfs(pNode start,pNode end);
void init_lookup_table();
int try_to_insert(int s);
int main()
{
Node start,end;
input(&start);
input(&end);
bfs(&start,&end);
printf("-1\n");
return 0;
}
void input(pNode start)
{
int i,j;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
scanf("%c",&( (start->tab)[i][j] ));
if((start->tab)[i][j]=='.')
{
start->x = i;
start->y = j;
}
}
}
start->no = 0;
getchar();
}
void bfs(pNode start,pNode end)
{
int i,j;
char ch;
pNode tmp;
init_lookup_table();
memcpy(&res[rear],start,sizeof(res[rear]));
try_to_insert(rear);
rear++;
while(front!=rear)
{
//printf("%d ",rear);
tmp = &res[front];
if(memcmp(tmp->tab,end->tab,sizeof(end->tab))==0)
{
printf("%d\n",tmp->no);
exit(0);
}
int no = tmp->no;
for(i=0;i<4;i++)
{
int xx = tmp->x+vx[i];
int yy = tmp->y+vy[i];
if(xx>=0 && xx<3 && yy>=0 && yy<3)
{
pNode p = &res[rear];
memcpy(p,tmp,sizeof(res[front]));
p->tab[tmp->x][tmp->y] = p->tab[xx][yy];
p->tab[xx][yy] = tmp->tab[tmp->x][tmp->y];
p->no = no+1;
p->x = xx;
p->y = yy;
if(try_to_insert(rear))
{
rear++;
}
}
}
front++;
//printf("%d ",rear);
}
}
void init_lookup_table()
{
int i;
fact[0] = 1;
for(i=1;i<9;i++)
{
fact[i] = fact[i-1]*i;
}
}
int try_to_insert(int s)
{
int i,j;
int code = 0;
for(i=0;i<9;i++)
{
int cnt = 0;
for(j=i+1;j<9;j++)
{
if(res[s].tab[j/3][j%3] < res[s].tab[i/3][i%3])
{
cnt++;
}
code += fact[8-i]*cnt;
}
}
if(vis[code])
{
return 0;
}
return vis[code] = 1;
}
>
历届试题 公式求值
问题描述 输入n, m, k，输出下面公式的值。
图片请百度
其中C_n^m是组合数，表示在n个人的集合中选出m个人组成一个集合的方案数。组合数的计算公式如下。
图片请百度
输入格式 输入的第一行包含一个整数n；第二行包含一个整数m，第三行包含一个整数k。 输出格式 计算上面公式的值，由于答案非常大，请输出这个值除以999101的余数。 样例输入 3 1 3 样例输出 162 样例输入 20 10 10 样例输出 359316 数据规模和约定 对于10%的数据，n≤10，k≤3； 对于20%的数据，n≤20，k≤3； 对于30%的数据，n≤1000，k≤5； 对于40%的数据，n≤10^7，k≤10； 对于60%的数据，n≤10^15，k ≤100； 对于70%的数据，n≤10^100，k≤200； 对于80%的数据，n≤10^500，k ≤500； 对于100%的数据，n在十进制下不超过1000位，即1≤n<10^1000，1≤k≤1000，同时0≤m≤n，k≤n。 提示 999101是一个质数； 当n位数比较多时，绝大多数情况下答案都是0，但评测的时候会选取一些答案不是0的数据；
>
历届试题 回文数字
问题描述 观察数字：12321，123321 都有一个共同的特征，无论从左到右读还是从右向左读，都是相同的。这样的数字叫做：回文数字。
本题要求你找到一些5位或6位的十进制数字。满足如下要求： 该数字的各个数位之和等于输入的整数。 输入格式 一个正整数 n (10<n<100), 表示要求满足的数位和。 输出格式 若干行，每行包含一个满足要求的5位或6位整数。 数字按从小到大的顺序排列。 如果没有满足条件的，输出：-1 样例输入 44 样例输出 99899 499994 589985 598895 679976 688886 697796 769967 778877 787787 796697 859958 868868 877778 886688 895598 949949 958859 967769 976679 985589 994499 样例输入 60 样例输出 -1
#include<stdio.h>
int main()
{
int a,b,c;
int n;
int flag=-1;
scanf(“%d”,&n);
for(a=1;a<10;a++)
{
for(b=0;b<10;b++)
{
for(c=0;c<10;c++)
{
if(a+b+c+b+a==n)
{
flag=1;
printf(“%d%d%d%d%d\n”,a,b,c,b,a);
}
}
}
}
for(a=1;a<10;a++)
{
for(b=0;b<10;b++)
{
for(c=0;c<10;c++)
{
if(a+b+c+c+b+a==n)
{
printf(“%d%d%d%d%d%d\n”,a,b,c,c,b,a);
flag=1;
}
}
}
}
if(flag==-1)
printf(“%d\n”,flag);
return 0;
}
>
历届试题 国王的烦恼
问题描述 C国由n个小岛组成，为了方便小岛之间联络，C国在小岛间建立了m座大桥，每座大桥连接两座小岛。两个小岛间可能存在多座桥连接。然而，由于海水冲刷，有一些大桥面临着不能使用的危险。
如果两个小岛间的所有大桥都不能使用，则这两座小岛就不能直接到达了。然而，只要这两座小岛的居民能通过其他的桥或者其他的小岛互相到达，他们就会安然无事。但是，如果前一天两个小岛之间还有方法可以到达，后一天却不能到达了，居民们就会一起抗议。
现在C国的国王已经知道了每座桥能使用的天数，超过这个天数就不能使用了。现在他想知道居民们会有多少天进行抗议。 输入格式 输入的第一行包含两个整数n, m，分别表示小岛的个数和桥的数量。 接下来m行，每行三个整数a, b, t，分别表示该座桥连接a号和b号两个小岛，能使用t天。小岛的编号从1开始递增。 输出格式 输出一个整数，表示居民们会抗议的天数。 样例输入 4 4 1 2 2 1 3 2 2 3 1 3 4 3 样例输出 2 样例说明 第一天后2和3之间的桥不能使用，不影响。 第二天后1和2之间，以及1和3之间的桥不能使用，居民们会抗议。 第三天后3和4之间的桥不能使用，居民们会抗议。 数据规模和约定 对于30%的数据，1<=n<=20，1<=m<=100； 对于50%的数据，1<=n<=500，1<=m<=10000； 对于100%的数据，1<=n<=10000，1<=m<=100000，1<=a, b<=n， 1<=t<=100000。
#include<stdio.h>
#include<malloc.h>
int a[100001],b[100001],c[100001],d[10001];
struct tubiao
{
int n;
struct tubiao *next;
}tu[10001];
void add(int u,int v)
{
struct tubiao p=(struct tubiao) malloc(sizeof(struct tubiao));
p->n=v;
p->next=NULL;
struct tubiao *q=&tu[u];
while(q->next)
{ q=q->next;
}
q->next=p;
}
void paixu(int first,int last)
{ if(first<last)
{
int i=first,j=last,ka=a[first],kb=b[first],kc=c[first];
while(i<j)
{
while(i<j&&kc<=c[j])
j–;
a[i]=a[j];b[i]=b[j];c[i]=c[j];
while(i<j&&kc>=c[i])
i++;
a[j]=a[i];b[j]=b[i];c[j]=c[i];
}
a[i]=ka;b[i]=kb;c[i]=kc;
paixu(first,i-1);
paixu(i+1,last);
}
}
int f1(int i)
{
if(d[i]==i)
return i;
int u=f1(d[i]);
d[i]=u;
return d[i];
}
int main()
{
int n,m,i1,u,v,t,i2;
scanf(“%d%d”,&n,&m);
for(i1=0;i1<m;i1++)
{ scanf(“%d%d%d”,&u,&v,&t);
a[i1]=u;b[i1]=v;c[i1]=t;
add(u,v);
add(v,u);
}
paixu(0,m-1);
int total=0,tianshu=0;
for(i1=1;i1<=n;i1++)
d[i1]=i1;
for(i1=m-1;i1>=0;i1–)
{ int ko=f1(a[i1]);
int ok=f1(b[i1]);
if(ko==ok)
{
continue;
}
else
{
d[ko]=b[i1];
if(tianshu!=c[i1])
{
total++;
tianshu=c[i1];
}
}
}
printf(“%d\n”,total);
return 0;
}
>
历届试题 数字游戏
问题描述 栋栋正在和同学们玩一个数字游戏。
游戏的规则是这样的：栋栋和同学们一共n个人围坐在一圈。栋栋首先说出数字1。接下来，坐在栋栋左手边的同学要说下一个数字2。再下面的一个同学要从上一个同学说的数字往下数两个数说出来，也就是说4。下一个同学要往下数三个数，说7。依次类推。
为了使数字不至于太大，栋栋和同学们约定，当在心中数到 k-1 时，下一个数字从0开始数。例如，当k=13时，栋栋和同学们报出的前几个数依次为： 1, 2, 4, 7, 11, 3, 9, 3, 11, 7。
游戏进行了一会儿，栋栋想知道，到目前为止，他所有说出的数字的总和是多少。 输入格式 输入的第一行包含三个整数 n,k,T，其中 n 和 k 的意义如上面所述，T 表示到目前为止栋栋一共说出的数字个数。 输出格式 输出一行，包含一个整数，表示栋栋说出所有数的和。 样例输入 3 13 3 样例输出 17 样例说明 栋栋说出的数依次为1, 7, 9，和为17。 数据规模和约定 1 < n,k,T < 1,000,000；
#include <stdio.h>
#include <windows.h>3
int s[1000000];
// 3 13 9
// 1 2 4 7 11 3 9 3 11 7 4 2 1 1 2 4 7 11 3 9 3 11 7 4 2 1
int main()
{
long long n,k,t,i,j=1,g=1,z,sum=0;
scanf(“%I64d%I64d%I64d”,&n,&k,&t);
if(k%2==0) z=k*2;
else z=k;
s[0]=1;
do //开始制表
{
j+=g;
if(j>=k) j%=k;
s[g]=j;
g++;
}
while(g<=z) ;
k=0;
for(i=0;i<t;i++)
{
sum+=s[k];
k+=n;
if(k>g-1) k-=g-1;
}
printf(“%I64d”,sum);
system(“pause”);
return 0;
}
>
历届试题 邮局
问题描述 C村住着n户村民，由于交通闭塞，C村的村民只能通过信件与外界交流。为了方便村民们发信，C村打算在C村建设k个邮局，这样每户村民可以去离自己家最近的邮局发信。
现在给出了m个备选的邮局，请从中选出k个来，使得村民到自己家最近的邮局的距离和最小。其中两点之间的距离定义为两点之间的直线距离。 输入格式 输入的第一行包含三个整数n, m, k，分别表示村民的户数、备选的邮局数和要建的邮局数。 接下来n行，每行两个整数x, y，依次表示每户村民家的坐标。 接下来m行，每行包含两个整数x, y，依次表示每个备选邮局的坐标。 在输入中，村民和村民、村民和邮局、邮局和邮局的坐标可能相同，但你应把它们看成不同的村民或邮局。 输出格式 输出一行，包含k个整数，从小到大依次表示你选择的备选邮局编号。（备选邮局按输入顺序由1到m编号） 样例输入 5 4 2 0 0 2 0 3 1 3 3 1 1 0 1 1 0 2 1 3 2 样例输出 2 4 数据规模和约定 对于30%的数据，1<=n<=10，1<=m<=10，1<=k<=5； 对于60%的数据，1<=m<=20； 对于100%的数据，1<=n<=50，1<=m<=25，1<=k<=10。
#include <stdio.h>
#include <math.h>
using namespace std;
struct Point {
int no;
int x, y;
double getDist(Point p) {
return sqrt((x - p.x) * (x - p.x) + (y - p.y) * (y - p.y));
}
};
Point ans[10];
int n, m, k;
Point person[50];
Point fire[25];
Point result[10];
bool repeat[50], ban[50];
double ansDist = 1000000000;
double minDist[50], sum = 0;
double G[50][25];
void dfs(int deep, int index)
{
if(deep == k) {
if(sum < ansDist) {
ansDist = sum;
for(int i = 0; i < k; i++) {
ans[i] = result[i];
}
}
} else {
double tmpDist[50] = {0}, tsum = sum;
bool flag2 = false;
for(int i = 0; i < n; i++)
tmpDist[i] = minDist[i];
for(int i = m-k+deep; i >= index; i–) {
if(repeat[i]) continue;
if(deep > 0 && ban[i]) continue;
bool flag = false;
if(deep == 0) {
sum = 0;
for(int j = 0; j < n; j++) {
minDist[j] = G[j][i];
sum += G[j][i];
}
flag = true;
}
else {
sum = tsum;
for(int j = 0; j < n; j++) {
if(G[j][i] < tmpDist[j]) {
sum -= tmpDist[j] - G[j][i];
minDist[j] = G[j][i];
flag = true;
} else minDist[j] = tmpDist[j];
}
}
if(flag) {
flag2 = true;
result[deep] = fire[i];
dfs(deep+1, result[deep].no + 1);
} else {
ban[i] = true;
}
}
if(flag2 == false) {
result[deep] = fire[result[deep-1].no+1];
dfs(deep+1, m-k+deep+1);
} else {
sum = tsum;
for(int j = 0; j < n; j++) {
minDist[j] = tmpDist[j];
}
}
}
}
int main()
{
scanf(“%d%d%d”, &n, &m, &k);
for(int i = 0; i < n; i++) {
scanf(“%d%d”, &person[i].x, &person[i].y);
minDist[i] = ansDist;
}
for(int i = 0; i < m; i++) {
scanf(“%d%d”, &fire[i].x, &fire[i].y);
fire[i].no = i;
}
for(int i = 0; i < m; i++) {
if(!repeat[i]) {
for(int j = i+1; j < m; j++)
if(fire[i].x == fire[j].x && fire[i].y == fire[j].y)
repeat[j] = true;
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
G[i][j] = person[i].getDist(fire[j]);
dfs(0, 0);
for(int i = 0; i < k; i++) {
printf(“%d “, ans[i].no+1);
}
return 0;
}
>
历届试题 城市建设
问题描述 栋栋居住在一个繁华的C市中，然而，这个城市的道路大都年久失修。市长准备重新修一些路以方便市民，于是找到了栋栋，希望栋栋能帮助他。
C市中有n个比较重要的地点，市长希望这些地点重点被考虑。现在可以修一些道路来连接其中的一些地点，每条道路可以连接其中的两个地点。另外由于C市有一条河从中穿过，也可以在其中的一些地点建设码头，所有建了码头的地点可以通过河道连接。
栋栋拿到了允许建设的道路的信息，包括每条可以建设的道路的花费，以及哪些地点可以建设码头和建设码头的花费。
市长希望栋栋给出一个方案，使得任意两个地点能只通过新修的路或者河道互达，同时花费尽量小。 输入格式 输入的第一行包含两个整数n, m，分别表示C市中重要地点的个数和可以建设的道路条数。所有地点从1到n依次编号。 接下来m行，每行三个整数a, b, c，表示可以建设一条从地点a到地点b的道路，花费为c。若c为正，表示建设是花钱的，如果c为负，则表示建设了道路后还可以赚钱（比如建设收费道路）。 接下来一行，包含n个整数w_1, w_2, …, w_n。如果w_i为正数，则表示在地点i建设码头的花费，如果w_i为-1，则表示地点i无法建设码头。 输入保证至少存在一个方法使得任意两个地点能只通过新修的路或者河道互达。 输出格式 输出一行，包含一个整数，表示使得所有地点通过新修道路或者码头连接的最小花费。如果满足条件的情况下还能赚钱，那么你应该输出一个负数。 样例输入 5 5 1 2 4 1 3 -1 2 3 3 2 4 5 4 5 10 -1 10 10 1 1 样例输出 9 样例说明 建设第2、3、4条道路，在地点4、5建设码头，总的花费为9。 数据规模和约定 对于20%的数据，1<=n<=10，1<=m<=20，0<=c<=20，w_i<=20； 对于50%的数据，1<=n<=100，1<=m<=1000，-50<=c<=50，w_i<=50； 对于70%的数据，1<=n<=1000； 对于100%的数据，1 <= n <= 10000，1 <= m <= 100000，-1000<=c<=1000，-1<=w_i<=1000，w_i≠0。
#include<cstdio>
#include<algorithm>
using namespace std;
const int NO=100006;
const int INF=1000000000;
struct R
{
int a,b,w;
}r[NO*10];
int fa[NO];
int n,m,sum;
void reset_fa()
{
for(int i=0;i<=n;i++)
fa[i]=i;
}
bool comp(const R &a,const R &b){return a.w<b.w;}
int find(int k){return k==fa[k]?k:fa[k]=find(fa[k]);}
int kruskal()
{
int i,num=0,a,b,k;
for(i=1;i<=m;i++)
{
a=find(r[i].a);
b=find(r[i].b);
if(a!=b)
{
if(r[i].a==0)
{
num++;
k=r[i].w;
}
sum+=r[i].w;
fa[a]=b;
}
}
if(num==1)
{
sum-=k;
}
return sum;
}
int main()
{
int i=1,j,a,b;
scanf(“%d%d”,&n,&m);
reset_fa();
while(m–)
{
scanf(“%d%d%d”,&r[i].a,&r[i].b,&r[i].w);
if(r[i].w<0)
{
sum+=r[i].w;
a=find(r[i].a);
b=find(r[i].b);
if(a!=b)
fa[a]=b;
}
else
i++;
}
for(j=1;j<=n;j++)
{
scanf(“%d”,&a);
if(a!=-1)
{
r[++i].a=0;
r[i].b=j;
r[i].w=a;
}
}
m=i;
sort(r+1,r+1+m,comp);
printf(“%d\n”,kruskal());
return 0;
}
>
历届试题 最大子阵
问题描述 给定一个n*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。
其中，A的子矩阵指在A中行和列均连续的一块。 输入格式 输入的第一行包含两个整数n, m，分别表示矩阵A的行数和列数。 接下来n行，每行m个整数，表示矩阵A。 输出格式 输出一行，包含一个整数，表示A中最大的子矩阵中的元素和。 样例输入 3 -1 -4 3 4 -1 -5 -2 8 样例输出 样例说明 取最后一列，和为10。 数据规模和约定 对于50%的数据，1<=n, m<=50； 对于100%的数据，1<=n, m<=500，A中每个元素的绝对值不超过5000。
#include “stdio.h”
#include “string.h”
int a[500][500],b[500];
int f(int n,int m)
{int i,j,k,t,max=-999999;
for(i=0;i<n;i++)
{memset(b,0,m*sizeof(int));
for(j=i;j<n;j++)
{t=-999999;
for(k=0;k<m;k++)
{b[k]+=a[j][k];
t+=b[k];
if(t<b[k])t=b[k];
if(max<t)max=t;
}
}
}
return max;
}
int main()
{
int i,j,n,m;
scanf(“%d%d”,&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf(“%d”,&a[i][j]);
printf(“%d”,f(n,m));
return 0;
}
>
历届试题 蚂蚁感冒
问题描述 长100厘米的细长直杆子上有n只蚂蚁。它们的头有的朝左，有的朝右。
每只蚂蚁都只能沿着杆子向前爬，速度是1厘米/秒。
当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。
这些蚂蚁中，有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。
请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。 输入格式 第一行输入一个整数n (1 < n < 50), 表示蚂蚁的总数。
接着的一行是n个用空格分开的整数 Xi (-100 < Xi < 100), Xi的绝对值，表示蚂蚁离开杆子左边端点的距离。正值表示头朝右，负值表示头朝左，数据中不会出现0值，也不会出现两只蚂蚁占用同一位置。其中，第一个数据代表的蚂蚁感冒了。 输出格式 要求输出1个整数，表示最后感冒蚂蚁的数目。 样例输入 3 5 -2 8 样例输出 1 样例输入 5 -10 8 -20 12 25 样例输出 3
#include <stdio.h>
struct mayi
{
int direct; //0为左，1为右
int dist; //距离左端点距离
int cold; //0为正常，1为感冒
} ;
int main()
{
int n,i,sign,j,num=0;
scanf(“%d”,&n);
struct mayi a[n];
for(i=0;i<n;i++)
{
scanf(“%d”,&a[i].dist);
a[i].dist*=2;
a[i].direct=1;
a[i].cold=0;
if(a[i].dist<0)
{
a[i].dist*=-1;
a[i].direct=0;
}
a[0].cold=1;
}
for(;;)
{
sign=0;
for(i=0;i<n;i++) //所有蚂蚁走路
{
if(a[i].direct==0) a[i].dist–;
else a[i].dist++;
}
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
if(a[i].dist==a[j].dist)
{
if(a[i].direct==0)
{a[i].direct=1; }
else a[i].direct=0;
if(a[j].direct==0)
{ a[j].direct=1;}
else a[j].direct=0;
if(a[i].cold==1 ) a[j].cold=1;
if(a[j].cold==1 ) a[i].cold=1;
}
}
for(i=0;i<n;i++)
{
if(a[i].dist>=0 && a[i].dist<=200)
{
sign=1;
break;
}
}
if(sign==0) break;
}
for(i=0;i<n;i++)
{
if(a[i].cold==1) num++;
}
printf(“%d\n”,num);
return 0;
}
>
历届试题 地宫取宝
问题描述 X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。
地宫的入口在左上角，出口在右下角。
小明被带到地宫的入口，国王要求他只能向右或向下行走。
走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿）。
当小明走到出口时，如果他手中的宝贝恰好是k件，则这些宝贝就可以送给小明。
请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。 输入格式 输入一行3个整数，用空格分开：n m k (1<=n,m<=50, 1<=k<=12)
接下来有 n 行数据，每行有 m 个整数 Ci (0<=Ci<=12)代表这个格子上的宝物的价值 输出格式 要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。 样例输入 2 2 2 1 2 2 1 样例输出 2 样例输入 2 3 2 1 2 3 2 1 5 样例输出 14
#include<stdio.h>
#include<string.h>
#define N 55
#define MOD 1000000007
int map[55][55];
int dp[55][55][15][15];
int main(void)
{
int n, m, k;
int i, j, c, val, aMax;
scanf(“%d%d%d”, &n, &m, &k);
aMax = 0;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= m; j++)
{
scanf(“%d”, &map[i][j]);
// map[i][j]++;
if(aMax < map[i][j])
{
aMax = map[i][j];
}
}
}
memset(dp, 0, sizeof(dp));
dp[1][1][0][0] = 1;
dp[1][1][1][map[1][1]] = 1;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= m; j++)
{
dp[i][j][0][0] += dp[i][j - 1][0][0] + dp[i - 1][j][0][0];
dp[i][j][0][0] %= MOD;
for(c = 1; c <= k; c++)
{
for(val = 0; val <= aMax; val++)
{
dp[i][j][c][val] += dp[i][j - 1][c][val] + dp[i - 1][j][c][val];
dp[i][j][c][val] %= MOD;
}
if(c == 1)
{
dp[i][j][1][map[i][j]] += dp[i][j - 1][0][0];
dp[i][j][1][map[i][j]] %= MOD;
dp[i][j][1][map[i][j]] += dp[i - 1][j][0][0];
dp[i][j][1][map[i][j]] %= MOD;
}
else
{
for(val = 0; val < map[i][j]; val++)
{
dp[i][j][c][map[i][j]] += dp[i][j - 1][c - 1][val];
dp[i][j][c][map[i][j]] %= MOD;
dp[i][j][c][map[i][j]] += dp[i - 1][j][c - 1][val];
dp[i][j][c][map[i][j]] %= MOD;
}
}
}
}
}
int sum = 0;
for(i = 0; i <= aMax; i++)
{
sum += dp[n][m][k][i];
sum %= MOD;
}
printf(“%d”, sum);
return 0;
}
>
历届试题 斐波那契
问题描述 斐波那契数列大家都非常熟悉。它的定义是：
f(x) = 1 …. (x=1,2) f(x) = f(x-1) + f(x-2) …. (x>2)
对于给定的整数 n 和 m，我们希望求出： f(1) + f(2) + … + f(n) 的值。但这个值可能非常大，所以我们把它对 f(m) 取模。 公式如下 图片百度
但这个数字依然很大，所以需要再对 p 求模。 输入格式 输入为一行用空格分开的整数 n m p (0 < n, m, p < 10^18) 输出格式 输出为1个整数，表示答案 样例输入 2 3 5 样例输出 0 样例输入 15 11 29 样例输出 25
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
#define PB push_back
#define MP make_pair
#define AA first
#define BB second
#define OP begin()
#define ED end()
#define SZ size()
#define SORT(x) sort(x.OP,x.ED)
#define SQ(x) ((x)(x))
#define SSP system(“pause”)
#define cmin(x,y) x=min(x,y)
#define cmax(x,y) x=max(x,y)
typedef long long LL;
typedef pair<int, int> PII;
const double eps=1e-8;
const double INF=1e20;
const double PI=acos( -1. );
const int MXN = 50;
const LL MOD = 1000000007;
LL llmul( LL a,LL b,LL mod ) {
a%=mod;a+=mod;a%=mod;
b%=mod;b+=mod;b%=mod;
if ( a<b )swap( a,b );
LL ret=0;
while ( b ) {
if ( b&1 )ret=( ret+a )%mod;
a=( a<<1 )%mod;
b/=2;
}
return ret;
}
struct matrix {
LL x[3][3];
matrix() {memset( x,0,sizeof x );}
};
matrix mmul( matrix &A,matrix &B,LL mod ) {
matrix ret;
for ( int i=1; i<=2; i++ )
for ( int j=1; j<=2; j++ )
for ( int k=1; k<=2; k++ )
ret.x[i][j]=( ret.x[i][j]+llmul( A.x[i][k],B.x[k][j],mod ) )%mod;
return ret;
}
matrix E;
matrix A;
LL fib( LL n,LL mod ) {
matrix O=E,B=A;
while ( n ) {
if ( n&1 )O=mmul( O,B,mod );
B=mmul( B,B,mod );
n/=2;
}
return O.x[1][2];
}
LL solve( LL n,LL m,LL mod ) {
LL t=n/m;
LL p=t/2,q=t%2;
LL fuhao=pm%2==0?1:-1;
if ( q==0 ) {
LL ans=fib( n%m,mod )*fuhao;
ans%=mod;
ans+=mod;
return ans%mod;
}
if ( n%m==0 )return 0;
LL x=(llmul(fib(n%m,mod),fib(m-1,mod),mod)*fuhao%mod+mod)%mod;
LL y=fib(m,mod);
LL a=fib(n%m-1,mod);
if(n%m%2==0)a–;
if(fuhao<0)a++;
a=(a%mod+mod)%mod;
return ((x-llmul(a,y,mod))%mod+mod)%mod;
}
int main() {
int i,j;
A.x[1][2]=A.x[2][1]=A.x[2][2]=1;
E.x[1][1]=E.x[2][2]=1;
LL n,m,mod;
while ( cin>>n>>m>>mod )
cout<<( solve( n+2,m,mod )-1+mod )%mod<<endl;
return 0;
}
>
历届试题 波动数列
问题描述 观察这个数列： 1 3 0 2 -1 1 -2 …
这个数列中后一项总是比前一项增加2或者减少3。
栋栋对这种数列很好奇，他想知道长度为 n 和为 s 而且后一项总是比前一项增加a或者减少b的整数数列可能有多少种呢？ 输入格式 输入的第一行包含四个整数 n s a b，含义如前面说述。 输出格式 输出一行，包含一个整数，表示满足条件的方案数。由于这个数很大，请输出方案数除以100000007的余数。 样例输入 4 10 2 3 样例输出 2 样例说明 这两个数列分别是2 4 1 3和7 4 1 -2。 数据规模和约定 对于10%的数据，1<=n<=5，0<=s<=5，1<=a,b<=5； 对于30%的数据，1<=n<=30，0<=s<=30，1<=a,b<=30； 对于50%的数据，1<=n<=50，0<=s<=50，1<=a,b<=50； 对于70%的数据，1<=n<=100，0<=s<=500，1<=a, b<=50； 对于100%的数据，1<=n<=1000，-1,000,000,000<=s<=1,000,000,000，1<=a, b<=1,000,000。
#define mod 100000007
int n,s,a,b,x[1001][1001],i,j,t;
fun()
{
while(x[i+1][t]>=mod)x[i+1][t]-=mod;
}
int main()
{
scanf(“%d%d%d%d”,&n,&s,&a,&b);
b%=n;
b*=-1;
while(b<0)b+=n;
a%=n;
s%=n;
while(s<0)s+=n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
x[i][j]=0;
x[1][a]=x[1][b]=1;
for(i=1;i<n-1;i++)
for(j=0;j<n;j++)
{
t=(j+a*(i+1))%n;
x[i+1][t]+=x[i][j];
fun();
t=(j+b*(i+1))%n;
if(t>=n)
t-=n;
x[i+1][t]+=x[i][j];
fun();
}
printf(“%d\n”,x[n-1][s]);
return 0;
}
>
历届试题 小朋友排队
问题描述 n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。
每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。
如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。
请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。
如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。 输入格式 输入的第一行包含一个整数n，表示小朋友的个数。 第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。 输出格式 输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。 样例输入 3 3 2 1 样例输出 9 样例说明 首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。 数据规模和约定 对于10%的数据， 1<=n<=10； 对于30%的数据， 1<=n<=1000； 对于50%的数据， 1<=n<=10000； 对于100%的数据，1<=n<=100000，0<=Hi<=1000000。
#include<stdio.h>
int h[100100];
int un[100100];
int b[1000100];
int reb[1000100];
int Lowbit(int x){
return x&(x^(x-1));
}
int sum(int bit[], int idx){
int ret = 0;
while(idx > 0){
ret += bit[idx];
idx -= Lowbit(idx);
}
return ret;
}
void add(int bit[], int idx, int val){
while(idx < 1000100){
bit[idx] += val;
idx += Lowbit(idx);
}
}
long long uVal[100100];
int main(void){
int n, i;
scanf(“%d”, &n);
uVal[0] = 0;
for(i = 0; i < n; i++){
scanf(“%d”, &h[i]);
h[i]++;
uVal[i + 1] = uVal[i] + i + 1;
un[i] += i - sum(b, h[i]);
add(b, h[i], 1);
}
long long ans = 0;
for(i = n - 1; i >= 0; i–){
un[i] += sum(reb, h[i] - 1);
add(reb, h[i], 1);
ans += uVal[un[i]];
}
printf(“%I64d\n”, ans);
return 0;
}
>
历届试题 分糖果
问题描述 有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果，然后进行下面的游戏：
每个小朋友都把自己的糖果分一半给左手边的孩子。
一轮分糖后，拥有奇数颗糖的孩子由老师补给1个糖果，从而变成偶数。
反复进行这个游戏，直到所有小朋友的糖果数都相同为止。
你的任务是预测在已知的初始糖果情形下，老师一共需要补发多少个糖果。 输入格式 程序首先读入一个整数N(2<N<100)，表示小朋友的人数。 接着是一行用空格分开的N个偶数（每个偶数不大于1000，不小于2） 输出格式 要求程序输出一个整数，表示老师需要补发的糖果数。 样例输入 3 2 2 4 样例输出 4
#include <stdio.h>
#include <malloc.h>
int count=0;
void f(int n,int *m)
{
int j,temp=m[0];
for(j=n-1;j>0;j–)
m[(j+1)%n]+=(m[j]/=2);
m[1]+=temp/2;
m[0]-=temp/2;
for(j=0;j<n;j++)
{
if(m[j]%2!=0)
{
m[j]++;
count++;
}
}
}
int jisuan(int n,int *m)
{
int j;
for(j=0;j<n-1;j++)
if(m[j]!=m[j+1]) return 0;
return 1;
}
int main()
{
int n,j;
scanf(“%d”,&n);
int m=(int)malloc(sizeof(int)*n);
for(j=0;j<n;j++)
scanf(“%d”,&m[j]);
do
{
f(n,m);
}
while(jisuan(n,m)!=1);
printf(“%d”,count);
return 0;
}
>
历届试题 兰顿蚂蚁
问题描述
图形百度 兰顿蚂蚁，是于1986年，由克里斯·兰顿提出来的，属于细胞自动机的一种。
平面上的正方形格子被填上黑色或白色。在其中一格正方形内有一只“蚂蚁”。 蚂蚁的头部朝向为：上下左右其中一方。
蚂蚁的移动规则十分简单： 若蚂蚁在黑格，右转90度，将该格改为白格，并向前移一格； 若蚂蚁在白格，左转90度，将该格改为黑格，并向前移一格。
规则虽然简单，蚂蚁的行为却十分复杂。刚刚开始时留下的路线都会有接近对称，像是会重复，但不论起始状态如何，蚂蚁经过漫长的混乱活动后，会开辟出一条规则的“高速公路”。
蚂蚁的路线是很难事先预测的。
你的任务是根据初始状态，用计算机模拟兰顿蚂蚁在第n步行走后所处的位置。 输入格式 输入数据的第一行是 m n 两个整数（3 < m, n < 100），表示正方形格子的行数和列数。 接下来是 m 行数据。 每行数据为 n 个被空格分开的数字。0 表示白格，1 表示黑格。
接下来是一行数据：x y s k, 其中x y为整数，表示蚂蚁所在行号和列号（行号从上到下增长，列号从左到右增长，都是从0开始编号）。s 是一个大写字母，表示蚂蚁头的朝向，我们约定：上下左右分别用：UDLR表示。k 表示蚂蚁走的步数。 输出格式 输出数据为两个空格分开的整数 p q, 分别表示蚂蚁在k步后，所处格子的行号和列号。 样例输入 5 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 3 L 5 样例输出 1 3 样例输入 3 3 0 0 0 1 1 1 1 1 1 1 1 U 6 样例输出 0 0
#include<stdio.h>
int a[1000][1000]={
0
};
char f(int i,char now)
{
if(i==0&&now==’U’||i==1&&now==’D’)
return ‘R’;
else if(i==0&&now==’R’||i==1&&now==’L’)
return ‘D’;
else if(i==0&&now==’D’||i==1&&now==’U’)
return ‘L’;
else if(i==0&&now==’L’||i==1&&now==’R’)
return ‘U’;
}
int main()
{
int n,m,i1,i2,x,y,k;
char s;
scanf(“%d%d”,&n,&m);
for(i1=0;i1<n;i1++)
for(i2=0;i2<m;i2++)
scanf(“%d”,&a[i1][i2]);
scanf(“%d%d”,&x,&y);
getchar();
scanf(“%c%d”,&s,&k);
char now=s;
while(k–)
{ if(a[x][y]==0)
a[x][y]=1;
else
a[x][y]=0;
now=f(a[x][y],now);
if(now==’U’)
x–;
else if(now==’D’)
x++;
else if(now==’L’)
y–;
else
y++;
}
printf(“%d %d\n”,x,y);
return 0;
}
>
历届试题 矩阵翻硬币
问题描述 小明先把硬币摆成了一个 n 行 m 列的矩阵。
随后，小明对每一个硬币分别进行一次 Q 操作。
对第x行第y列的硬币进行 Q 操作的定义：将所有第 i**x 行，第 j**y 列的硬币进行翻转。
其中i和j为任意使操作可行的正整数，行号和列号都是从1开始。
当小明对所有硬币都进行了一次 Q 操作后，他发现了一个奇迹——所有硬币均为正面朝上。
小明想知道最开始有多少枚硬币是反面朝上的。于是，他向他的好朋友小M寻求帮助。
聪明的小M告诉小明，只需要对所有硬币再进行一次Q操作，即可恢复到最开始的状态。然而小明很懒，不愿意照做。于是小明希望你给出他更好的方法。帮他计算出答案。 输入格式 输入数据包含一行，两个正整数 n m，含义见题目描述。 输出格式 输出一个正整数，表示最开始有多少枚硬币是反面朝上的。 样例输入 2 3 样例输出 1 数据规模和约定 对于10%的数据，n、m <= 10^3； 对于20%的数据，n、m <= 10^7； 对于40%的数据，n、m <= 10^15； 对于10%的数据，n、m <= 10^1000（10的1000次方）。
#include<stdio.h>
#include<string.h>
#define MAX 1000 + 10
int minu[MAX], sub[MAX], sq[MAX];
int x;
int main()
{
void sqrt_int ( char * , int ) ;
char n[MAX], m[MAX]; scanf ( “%s” , n ) ; scanf (“%s” , m ) ;
int a[MAX], b[MAX], s[MAX], S[MAX]; int c, i, j, k, na, nb;
int len_n , len_m ;
memset ( a, 0, sizeof (a) ) ; memset ( b, 0, sizeof (b) ) ;
memset ( s, 0, sizeof (s) ) ; memset ( S, 0, sizeof (S) ) ;
len_n = strlen (n) , len_m = strlen (m) ;
sqrt_int ( n, len_n ) ; for ( na = x, i = 0 ; x >= 0 ; i ++ ) a[i] = sq[x–] ;
sqrt_int ( m, len_m ) ; for ( nb = x, i = 0 ; x >= 0 ; i ++ ) b[i] = sq[x–] ;
for ( i = 0 ; i <= na ; i ++ )
{
for ( k = i, c = j = 0 ; j <= nb+1 ; j ++ , k ++ )
{
s[k] = (a[i] * b[j]) % 10 + c ;
c = (a[i] * b[j]) / 10 ;
if (s[k] >= 10 ) { s[k] -= 10 ; c ++ ; }
S[k] += s[k] ; if ( S[k] >= 10 ) { S[k] -= 10 ; S[k+1] ++ ; }
}
}
for ( i = MAX-1 ; i >= 0 ; i – ) if (S[i]) break ;
for ( j = i ; j >= 0 ; j – ) printf (“%d” , S[j] ) ;
putchar (‘\n’) ;
return 0;
}
void sqrt_int ( char minu_char , int len )
{
int i, j, k, m;
int s, c, flag;
int first, num;
memset ( minu, 0, sizeof (minu) ) ;
memset ( sub, 0, sizeof (sub) ) ;
memset ( sq, 0, sizeof (sq) ) ;
if ( len % 2 )
{
minu[0] = minu_char[0] - ‘0’ ;
for ( num = 3 ; num >= 0 ; num – ) if ( minu[0] >= numnum ) break ;
sq[x=0] = num ; minu[0] -= num*num ; first = 1 ;
}
else
{
sq[x=0] = 0 ; first = 0 ;
}
for ( i = first ; i < len ; i += 2 )
{
minu[i] = minu_char[i] - ‘0’ ; minu[i+1] = minu_char[i+1] - ‘0’ ;
memset (sub , 0, sizeof (sub) ) ;
for ( k = 9 ; k >= 0 ; k – )
{
sub[i+1] = k ; c = 0 ;
for ( m = i , j = x ; j >= 0 ; j – , m – )
{
s = sq[j] * 2 ;
sub[m] = s % 10 + c ;
c = s / 10 ;
}
sub[m] = c ; c = 0 ;
for ( m = i+1 ; m >= 0 ; m – )
{
s = sub[m] * k ;
sub[m] = s % 10 + c ;
c = s / 10 ;
if (sub[m] >= 10 ) { sub[m] -= 10 ; c ++ ; }
}
for ( flag = m = 0 ; m <= i+1 ; m ++ )
{
if (minu[m] < sub[m]) { flag = 1 ; break ; }
else if (minu[m] > sub[m] ) break ;
}
if ( !flag )
{
for ( m = i+1 ; m >= 0 ; m – )
{
if ( minu[m] < sub[m] ) { minu[m] += 10 ; minu[m-1] – ; }
minu[m] -= sub[m] ;
}
sq[++x] = k ; break ;
}
else memset (sub, 0, sizeof (sub) ) ;
}
}
}
```
转自：http://blog.csdn.net/rodestillfaraway/article/details/50529769
