2013安徽省大学生程序设计大赛题目与答案

2013安徽省省赛题解

2013.05.30

2013安徽省省赛裁判出题组

目录

A.单词反转 ....................................................................................................................................... 2 B.等差数列 ....................................................................................................................................... 4 C.进程调度 ....................................................................................................................................... 9 D.进击的巨人 ................................................................................................................................. 11 E.巨人的进击 ................................................................................................................................. 13 F.闪光的指压师 .............................................................................................................................. 17 G.Alice&Marisa .............................................................................................................................. 20 H.排列的前后 ................................................................................................................................. 22 I.散步 .............................................................................................................................................. 33 J.IQ test?和K.IQ test 2 ................................................................................................................... 36 L.the end of the world ..................................................................................................................... 38

A.单词反转

Solution:

简单的字符串处理，只要将一句话中的单词反转输出，其余字符原样输出即可。

Code：

#include #include #include

using namespace std;

bool isChar(char ch) {

return ( (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') ); }

int main() {

string s = \ string word = \ char ch; int cnt = 0; while (true) {

getline(cin, s); if (s.size() == 0) { break; }

word = \ int i, j, k;

for (i = 0; i < s.size(); ) { if (isChar(s[i])) { word = \ word += s[i];

for (j = i + 1; j < s.size(); ++j) { if (isChar(s[j])) { word += s[j]; } else { break; }

}

for (k = word.size() - 1; k >= 0; --k) { cout<

if (j >= s.size()) { break; } else {

cout<

i = j + 1; } else {

cout<

cout<

return 0; }

B.等差数列

Solution:

首先所说明一下，这题原定的时限是1s，比赛时为了降低难度将时限改为了10s。比赛时用O(n^2)的算法是可以过的。

要想在ls的时限下过这道题，就要用线段树。

考虑以下数列a：

1 2 3 4 6 8 10 12

我们将数列a的相邻两项相减得到数列b: _ 1 1 1 2 2 2 2 观察发现，要想求数列a的区间[L, R]上的最长等差数列的长度，只要求数列b的区间[L+1,R]上的最长连续相同数值的长度再加1。

现在将a[1,4]加上一个首项为A=2，公差为D=1的等差数列后，a为： 1 4 6 8 11 8 10 12 而这时的b为：

_ 3 2 2 3 -3 2 2

相当于将b[1]加上A=2，将b[2,4]加上D=1，将b[5]加上-(A+(R-1)*D)=-5。

Code:

#include #include #include

using namespace std;

const int maxn = 100010;

struct Node { int l, r, rt;

int llen, rlen; // 区间左（右）端点开始的连续数列长度 int mlen; // 区间最长连续数列的长度

long long lvalue, rvalue; // 区间左（右）端点数列的值 int len() {

return r - l + 1; }

}seg[maxn<<2];

void build(int l, int r, int rt)

{

seg[rt].l = l; seg[rt].r = r;

seg[rt].llen = seg[rt].rlen = seg[rt].mlen = seg[rt].len(); seg[rt].lvalue = seg[rt].rvalue = 0;

if (l == r) { return ; }

int mid = (l + r) >> 1; build(l, mid, rt << 1);

build(mid + 1, r, (rt << 1) | 1); }

void pushDown(int rt) {

if (seg[rt].mlen == seg[rt].len()) { int lch = rt << 1; int rch = (rt << 1) | 1;

seg[lch].llen = seg[lch].rlen = seg[lch].mlen = seg[lch].len(); seg[lch].lvalue = seg[rt].lvalue;

seg[rch].llen = seg[rch].rlen = seg[rch].mlen = seg[rch].len(); seg[rch].rvalue = seg[rt].rvalue; } }

void pushUp(int rt) {

int lch = rt << 1; int rch = (rt << 1) | 1;

seg[rt].lvalue = seg[lch].lvalue; seg[rt].rvalue = seg[rch].rvalue; seg[rt].llen = seg[lch].llen; seg[rt].rlen = seg[rch].rlen;

seg[rt].mlen = max(seg[lch].mlen, seg[rch].mlen);

if (seg[lch].len() == seg[lch].llen && seg[rch].lvalue == seg[lch].rvalue) { seg[rt].llen += seg[rch].llen; }

if (seg[rch].len() == seg[rch].rlen && seg[lch].rvalue == seg[rch].lvalue) { seg[rt].rlen += seg[lch].rlen; }

if (seg[lch].rvalue == seg[rch].lvalue) {

seg[rt].mlen = max(seg[rt].mlen, seg[lch].rlen + seg[rch].llen); } }

void update(int l, int r, int rt, long long d) {

if (l > r) {

return ; }

if (l == seg[rt].l && r == seg[rt].r) { if (seg[rt].mlen == seg[rt].len()) { seg[rt].lvalue += d; seg[rt].rvalue += d; return ; } }

pushDown(rt);

int mid = (seg[rt].l + seg[rt].r) / 2; int lch = rt << 1; int rch = (rt << 1) | 1; if (r <= mid) {

update(l, r, lch, d); } else if (l > mid) { update(l, r, rch, d); } else {

update(l, mid, lch, d); update(mid + 1, r, rch, d); }

pushUp(rt); }

int query(int l, int r, int rt) {

if (l > r) {

return 0; }

if (l == seg[rt].l && r == seg[rt].r) { return seg[rt].mlen; }

pushDown(rt);

int lch = (rt << 1); int rch = (rt << 1) | 1;

int mid = (seg[rt].l + seg[rt].r) >> 1;

if (r <= mid) {

return query(l, r, lch); } else if (l > mid) {

return query(l, r, rch); } else {

int mlen;

mlen = max(query(l, mid, lch), query(mid + 1, r, rch)); if (seg[lch].rvalue == seg[rch].lvalue) {

mlen = max(mlen, min(seg[lch].rlen, mid - l + 1) + min(seg[rch].llen, r - mid)); }

return mlen; } }

int main() {

//freopen(\等差数列.in\ //freopen(\等差数列.out\ int n, m; char op[10]; int L, R; int A, D; int tcase = 0;

while (scanf(\ tcase++;

printf(\ build(1, n - 1, 1);

for (int i = 0; i < m; ++i) { scanf(\ if (op[0] == 'A') {

scanf(\ if (L != 0) {

update(L, L, 1, A); }

if (L + 1 <= R) {

update(L + 1, R, 1, D); }

if(R != n - 1) {

update(R + 1, R + 1, 1, -(A + (R - 1) * D)); } } else {

scanf(\

printf(\ } } }

return 0; }

C.进程调度

Solution:

首先，将各进程先按到达时间由先到后，再按执行时间由短到长排序。排序后在模拟一下各进程的执行过程即可。排序时间复杂度为O(nlogn)，模拟时间复杂度为O(n)。

Code:

#include #include #include

using namespace std;

const int maxn = 1010;

struct Proc { int a, e; }p[maxn]; int n;

bool cmp(Proc p1, Proc p2) {

if (p1.a != p2.a) {

return p1.a < p2.a; }

return p1.e < p2.e; }

int main() {

//freopen(\进程调度.in\ //freopen(\进程调度.out\ while (scanf(\ for (int i = 0; i < n; ++i) {

scanf(\ }

sort(p, p + n, cmp); int waitTime = 0; int exeTime = 0; int endTime = p[0].a; for (int i = 0; i < n; ++i) {

if (p[i].a < endTime) {

waitTime += (endTime - p[i].a); exeTime += p[i].e; endTime += p[i].e; } else {

exeTime += p[i].e;

endTime = p[i].a + p[i].e; } }

printf(\ }

return 0; }

D.进击的巨人

其实这题应该可以水过去吧，就直接暴力枚举圆上的点，精度控制在合适的范围内，选出最大的距离即可，不过数据要是严一点的话，就过不了了。所以此题的标准做法是三分，因为起点到圆再到线段的距离满足凹函数的性质，故可以对弧度进行三分求解。此题是按[0,pi]和[pi,2pi]2部分分别进行三分求解，取最优值。 #include #include #include #include #define EPS 1e-6 #define PI acos(-1.0) using namespace std; struct point { double x,y,r; }start,line[2],cir;

double cross(const point &p1, const point &p2, const point &q1, const point &q2)//叉乘 {

return (q2.y - q1.y)*(p2.x - p1.x) - (q2.x - q1.x)*(p2.y - p1.y); }

double dis(const point &p, const point &q)//点与点的距离 {

return sqrt((p.x - q.x)*(p.x - q.x) + (p.y - q.y)*(p.y - q.y)); }

point rorate (const point &p , const double &angle)//按弧度枚举圆上的点 {

point ans,temp;

ans.x = p.x + p.r*cos(angle); ans.y = p.y + p.r*sin(angle); return ans; }

double dot(const point &p1, const point &p2, const point &q1, const point &q2)//点积 {

return (p2.x - p1.x)*(q2.x - q1.x) + (p2.y - p1.y)*(q2.y - q1.y); }

double dis_line(const point &p)//点到线段 {

if (dot(line[0],line[1],line[0],p)*dot(line[1],line[0],line[1],p) > 0) { return fabs(cross(line[0],line[1],line[0],p))/dis(line[0],line[1]); } else {

return min(dis(line[0],p),dis(line[1],p)); }

return 0; }

double thr_search(double angle, double st)//主要的部分，三分的程序 {

point temp1, temp2;

double l(st),r(angle),mid1,mid2; while (fabs(r - l) > EPS) { mid1 = (r + l)/2; mid2 = (mid1 + r)/2; temp1 = rorate(cir,mid1); temp2 = rorate(cir,mid2);

if (dis_line(temp1) + dis(temp1,start) <= dis_line(temp2) + dis(temp2,start))r = mid2; else l = mid1; }

temp1 = rorate(cir,l);

return dis_line(temp1) + dis(temp1,start); }

int main() {

//freopen(\ //freopen(\ int cnt = 0;

while (scanf(\ scanf(\

for (int i(0); i<2; i++)scanf(\ double angle = PI,st = 0;//先对[0,pi]进行三分 double ans = thr_search(angle,st);

angle += PI;st += PI;//再对[pi,2pi]进行三分 ans = min(ans,thr_search(angle,st)); printf(\ }

return 0; }

E.巨人的进击

此题数据很弱，而且测试数据也比较水，凸包的点只有20不到。这题的思路较为奇特，一般也不会往那方面想。那就是二分(-_-!!)，二分半径即可，然后将凸包所有边往凸包内平移这么半径长度,然后检验看平移后是否能围成凸包。 #include #include #include #include #include #include using namespace std; #define MAXN 110 #define eps 1e-10

#define zero(x) (((x)>0?(x):-(x))

double x,y; pt(){}

pt(double xx, double yy) {

x=xx; y=yy; } };

double dist(pt p1, pt p2)//点到点的距离 {

return sqrt(1.0*(p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y)); }

double Cross(pt a, pt b)//叉乘 {

return a.x*b.y - a.y*b.x; }

double Cross(pt a, pt b, pt c)//叉乘 {

return Cross(pt(a.x-c.x,a.y-c.y),pt(b.x-c.x,b.y-c.y)); }

double same_side(pt p1, pt p2, pt l1, pt l2)//同一面 {

return Cross(l1,p1,l2)*Cross(l1,p2,l2) > eps; }

struct Convex {

int n;

pt p[MAXN]; };

struct Plane//半平面,a,b构成直线,side表示在哪个面 {

pt a,b,side; }; /*

**ret.x-u1.x=t(u2.x-u1.x) **ret.y-u1.y=t(u2.y-u1.y) **ret.x-v1.x=tt(v2.x-v1.x) **ret.y-v1.y=tt(v2.y-v1.y)

**解以上方程可得线段交点ret */

pt intersection(pt u1, pt u2, pt v1, pt v2) {

pt ret = u1;

double t = ((u1.x - v1.x)*(v1.y - v2.y) - (u1.y - v1.y)*(v1.x - v2.x)) /((u1.x - u2.x)*(v1.y - v2.y) - (u1.y - u2.y)*(v1.x - v2.x)); ret.x += (u2.x - u1.x)*t; ret.y += (u2.y - u1.y)*t; return ret; }

Convex src,ans;

Convex Half_Plane(Convex c, Plane pl)//半平面交,一条直线切割凸包 {

int i,j;

double r1,r2;

Convex ans,ans1; ans.n = 0;

for(i = 0; i

if (same_side(c.p[i],pl.side,pl.a,pl.b)) ans.p[ans.n++] = c.p[i];

if ((!same_side(c.p[i],c.p[(i+1)%c.n],pl.a,pl.b))&&(!(zero(Cross(c.p[i],pl.a,pl.b)) && zero(Cross(c.p[(i+1)%c.n],pl.a,pl.b)))))

ans.p[ans.n++] = intersection(c.p[i],c.p[(i+1)%c.n],pl.a,pl.b); //有点在直线上的话该点会被加入两次 }

ans1.n = 0;

for(i = 0; i

if (!i || !zero(ans.p[i].x-ans.p[i-1].x) || !zero(ans.p[i].y-ans.p[i-1].y)) ans1.p[ans1.n++] = ans.p[i];//过滤重复点

if (zero(ans1.p[ans1.n-1].x-ans1.p[0].x) && zero(ans1.p[ans1.n-1].y-ans1.p[0].y)) ans1.n--; if (ans1.n < 3) ans1.n = 0; return ans1; }

bool judge(double x) {

Convex ans; pt tt,ta,tb; ans = src;

for (int i = 0; i < src.n; i++) {

tt.x = src.p[i].y - src.p[i+1].y; tt.y = src.p[i+1].x - src.p[i].x;

double k = x/sqrt(tt.x*tt.x + tt.y*tt.y); tt.x = tt.x*k; tt.y = tt.y*k;

ta.x = src.p[i].x + tt.x; ta.y = src.p[i].y + tt.y; tb.x = src.p[i+1].x + tt.x; tb.y = src.p[i+1].y + tt.y; Plane pl;

pl.a = ta;pl.b = tb;

pl.side.x = src.p[i].x + tt.x + tt.x; pl.side.y = src.p[i].y + tt.y + tt.y; ans = Half_Plane(ans,pl); if (ans.n == 0) return false; }

return true; }

int main(int argc, char** argv) {

//freopen(\ //freopen(\ int n,i,j,tcase; double maxl;

while(scanf(\ src.n = n; for(i = 0; i

scanf(\ src.p[n] = src.p[0]; double d,maxd = 0; for (i = 0; i

if ((d = dist(src.p[i],src.p[j])) > maxd) maxd = d; double l,r,mid,k,ansd; l = 0;r = maxd/2; ansd = 0;

while(l + eps < r) { mid = (l + r)/2; if (judge(mid)) { ansd = mid; l = mid + eps; } else {

r = mid - eps; } }

printf(\ }

return 0; }

F.闪光的指压师

水题一枚，注意一下如果是以非数字结尾的话，要加上ok。其他没什么难的了。 #include #include #include #include using namespace std; vector tab[10];

void ini() { tab[0].push_back(' '); tab[1].push_back(','); tab[1].push_back('.'); tab[1].push_back('!'); char temp = 'a'; for (int i(2),j(0); i<10; ++i) { tab[i].push_back(temp+j++); tab[i].push_back(temp+j++); tab[i].push_back(temp+j++);

if (i == 7 || i == 9)tab[i].push_back(temp+j++); } }

int get_kind(char a) { if (a <= 'z' && a >= 'a')return 0; if (a == ' ' || a == ',' || a == '.' || a == '!')return 0; if (a <= 'Z' && a >= 'A')return 1; if (a <= '9' && a >= '0')return 2; }

int get_key(char a, int &pos) {

if (a >= 'A' && a <= 'Z')a = 'a' + (a-'A'); for (int i(0); i<10; ++i) { for (int j(0); j

} } }

void same_kind(char a, char b)//0 ('a'-'z') (' ') (',') ('.') ('!') 1 ('A'-'Z') 2('0'-'9') { int numa = get_kind(a); int numb = get_kind(b); if ((numb == 0 && numa == 1) || (numb == 1 && numa == 0)) { cout<<\ } else { if ((numb == 0 && numa == 2) || (numb == 2 && numa == 0) || (numb == 1 && numa == 2) || (numb == 2 && numa == 1)) { cout<<\

if (numb == 1 && numa == 2)cout<<\ } } }

void same_key(char a, char b) { int pos = 0,nn = 0; int keya = get_key(a,pos); int keyb = get_key(b,nn); for (int i(0); i<=pos; ++i)cout<= '0'))cout<<\ } }

int main() {

//freopen(\ //freopen(\ string data; char now[1004]; ini(); while (getline(cin,data)) { now[0] = 'a'; for (int i(0); i

}

for (int i(1); i<=data.length(); ++i) { int j = i - 1; int k = i + 1; same_kind(now[j],now[i]); if (get_kind(now[i]) == 2) { cout<

return 0;

G.Alice&Marisa

本题的思路是确定胜利的条件。双方的策略都是尽可能平均的价格买到尽可能多的节操。一种情况是节操的数量足够多，多到可能出价为1都没有竞争了。另一种情况是节操的数量比较少，双方要拿到至少一半节操数量才能保证不会输。

由于每次都是由Marisa先出价，所以主要是比较N和CM的大小关系来确定。 (1) 当N > 2 *CM时

因为Marisa无法买到至少一半的节操，所以Marisa每次出价都为1。Alice的策略一样，即使前面的节操都让给Marisa后面还是有足够的节操让自己买。所以直接比较钱数，钱多的胜，相等的话则平局。 (2) 当N<=2*CM时

需要分奇偶讨论. <1>当N为奇数时

由于节操数量为奇数，所以不存在平局的情况(每个节操都会有买主)。获胜方需要拿到数量为w=N/2+1个节操才能获胜。Marisa先出价，所以策略是每次用p=CM/w的价格来买节操。Alice的策略则是每次以Marisa多1的价格来买节操。那么Alice需要(p+1)*w的钱才能保证必胜。所以CA>=(p+1)*w时,Alice必胜，否则Marisa胜。 <2>当N为偶数时。

此时可能平局需要数量为d=N/2，胜利需要的节操数量为w=N/2+1

Marisa为了拿到d个节操需要每次出价m1=CM/d，为了拿到w个节操需要每次出价m2=CM/w，m1较大,m2较小。如果无法胜利双方会优先保证平局，然后再考虑是否可以胜过对面，为了胜过对面的策略都是只花比对方平局多1的钱去买节操。Alice每次都出(m1+1)所以CA>=(m1+1)*w时，Alice必胜。因为Marisa先出价所以Marisa想胜利的条件是CA<(m2+1)*d则表示Alice无法达到平局条件，而Marisa至少可以达到平局，所以Marisa必胜。剩下的情况是2人平局。

*一定要尽可能平均的出价的原因是因为如果你有一个出价过高，则必须至少有另外一次出价会低于平均价，过高出价对手会直接放弃，而另一次低于平均价的出价就会被对手利用，这是有害的。

*注意以上的除法都是整除。如果除不尽的话，余数部分是直接舍弃的，因为决定胜利或者平局的永远是看你能不能拿到最后一个关键的节操。可能你之前以m1+1的价格拿到了d-1个节操，但是最后一个你只能出m1了，对手可以不停的出m1+1的价格来压过你的出价，所以最后一个关键节操你永远拿不到，对手将获得胜利，所以全部都是整除。 *需要注意数据中有0的情况 #include using namespace std; int main() {

int n,cm,ca;

while(cin>>n>>cm>>ca) {

if(n == 0)

cout<<0<

else if(n > 2 * cm) {

if(ca > cm)

cout<<-1<

cout<<1<

int winner = n / 2 +1; int draw = n / 2; if(n % 2 == 1) {

if (ca >= (cm / winner + 1 ) * winner) cout<<-1<

cout<<1<

if(ca >= (cm / draw + 1) * winner)//òto?cm?áéù?ü??μ????? cout<<-1<

else if (ca < (cm / winner + 1) * draw) cout<<1<

cout<<0<

H.排列的前后

我们都知道前m个字母构成的全排列的数量是m!(m的阶乘)，考虑将每个排列与一个具体的数字对应(0~m!-1)，比如ABCD对应0,DCBA对应23。转换的思路是变进制数。从左往右位开始，每一位分别是4进制，3进制，2进制，最后一位肯定只能是0(称之为1进制)，每一位字母代表的数字i表示的意思是它在它和它右边的字母中是第i+1小的。例如在ABCD中，ABCD在每一位代表的数字都是0。DCBA分别对应的数字是3,2,1,0。知道这个规则之后就可以把对应的排列转换为对应的数字，然后加上n再转换回排列即可。如果超出0~n!-1的范围就是不存在。省赛时数据范围已经更改，不需要高精度。不过在oj上添加的时候使用了强数据（即原数据范围），需要考虑高精度。这里的代码是无高精度版。 #include #include #include #include

using namespace std; //′óêy

#define MAXN 9999 #define MAXSIZE 10 #define DLEN 4 class BigNum {

private:

int a[500]; //?éò?????′óêyμ???êy int len; //′óêy3¤?è public:

BigNum(){ len = 1;memset(a,0,sizeof(a)); } //11?ìoˉêy BigNum(const int); //??ò???intààDíμ?±?á?×a?ˉ?a′óêy BigNum(const char*); //??ò???×?·?′?ààDíμ?±?á?×a?ˉ?a′óêy BigNum(const BigNum &); //??±′11?ìoˉêy BigNum &operator=(const BigNum &); //?????3?μ????·?￡?′óêy??????DD?3?μ????

friend istream& operator>>(istream&, BigNum&); //????ê?è?????·? friend ostream& operator<<(ostream&, BigNum&); //????ê?3?????·?

BigNum operator+(const BigNum &) const;

//?????ó·¨????·?￡?á???′óêy????μ??à?ó???? BigNum operator-(const BigNum &) const; //??????·¨????·?￡?á???′óêy????μ??à?????? BigNum operator*(const BigNum &) const; //????3?·¨????·?￡?á???′óêy????μ??à3????? BigNum operator/(const int &) const; //????3y·¨????·?￡?′óêy??ò?????êy??DD?à3y???? BigNum operator*(const int &) const; BigNum operator+(const int &) const;

BigNum operator^(const int &) const; //′óêyμ?n′?·????? int operator%(const int &) const; //′óêy??ò???intààDíμ?±?á???DDè??￡???? bool operator>(const BigNum & T)const; //′óêyoíáíò???′óêyμ?′óD?±è?? bool operator>(const int & t)const; //′óêyoíò???intààDíμ?±?á?μ?′óD?±è?? bool operator==(const BigNum & T)const; //′óêyoíáíò???′óêyμ??àμè±è?? bool operator==(const int & t)const; //′óêyoíò???intààDíμ?±?á?μ??àμè±è?? void print(); //ê?3?′óêy };

BigNum::BigNum(const int b) //??ò???intààDíμ?±?á?×a?ˉ?a′óêy {

int c,d = b; len = 0;

memset(a,0,sizeof(a)); while(d > MAXN) {

c = d - (d / (MAXN + 1)) * (MAXN + 1); d = d / (MAXN + 1); a[len++] = c; }

a[len++] = d; }

BigNum::BigNum(const char*s) //??ò???×?·?′?ààDíμ?±?á?×a?ˉ?a′óêy {

int t,k,index,l,i;

memset(a,0,sizeof(a)); l=strlen(s); len=l/DLEN; if(l%DLEN) len++; index=0;

for(i=l-1;i>=0;i-=DLEN) {

t=0;

k=i-DLEN+1;

if(k<0) k=0;

for(int j=k;j<=i;j++) t=t*10+s[j]-'0'; a[index++]=t; } }

BigNum::BigNum(const BigNum & T) : len(T.len) //??±′11?ìoˉêy {

int i;

memset(a,0,sizeof(a)); for(i = 0 ; i < len ; i++) a[i] = T.a[i]; } BigNum & BigNum::operator=(const BigNum //?????3?μ????·?￡?′óêy??????DD?3?μ???? {

int i;

len = n.len;

memset(a,0,sizeof(a)); for(i = 0 ; i < len ; i++) a[i] = n.a[i]; return *this; }

istream& operator>>(istream & in, BigNum & b) //????ê?è?????·? {

char ch[MAXSIZE*4]; int i = -1; in>>ch;

int l=strlen(ch); int count=0,sum=0; for(i=l-1;i>=0;) {

sum = 0; int t=1;

for(int j=0;j<4&&i>=0;j++,i--,t*=10) {

sum+=(ch[i]-'0')*t; }

b.a[count]=sum; count++; }

b.len =count++; return in;

& n)

}

ostream& operator<<(ostream& out, BigNum& b) //????ê?3?????·? {

int i;

cout << b.a[b.len - 1];

for(i = b.len - 2 ; i >= 0 ; i--) {

cout.width(DLEN); cout.fill('0'); cout << b.a[i]; }

return out; }

BigNum BigNum::operator+(const BigNum & T) const {

BigNum t(*this); int i,big; //??êy big = T.len > len ? T.len : len; for(i = 0 ; i < big ; i++) {

t.a[i] +=T.a[i]; if(t.a[i] > MAXN) {

t.a[i + 1]++;

t.a[i] -=MAXN+1; } }

if(t.a[big] != 0)

t.len = big + 1; else

t.len = big; return t; }

BigNum BigNum::operator-(const BigNum & T) const {

int i,j,big; bool flag; BigNum t1,t2; if(*this>T) {

t1=*this; t2=T;

//á???′óêy????μ??à?ó????//á???′óêy????μ??à?????? flag=0; } else {

t1=T; t2=*this; flag=1; }

big=t1.len;

for(i = 0 ; i < big ; i++) {

if(t1.a[i] < t2.a[i]) {

j = i + 1;

while(t1.a[j] == 0) j++; t1.a[j--]--; while(j > i)

t1.a[j--] += MAXN;

t1.a[i] += MAXN + 1 - t2.a[i]; } else

t1.a[i] -= t2.a[i]; }

t1.len = big;

while(t1.a[len - 1] == 0 && t1.len > 1) {

t1.len--; big--; }

if(flag)

t1.a[big-1]=0-t1.a[big-1]; return t1; }

BigNum BigNum::operator*(const BigNum & T) const {

BigNum ret; int i,j,up;

int temp,temp1; for(i = 0 ; i < len ; i++) {

up = 0;

for(j = 0 ; j < T.len ; j++)

//á???′óêy????μ??à3????? {

temp = a[i] * T.a[j] + ret.a[i + j] + up; if(temp > MAXN) {

temp1 = temp - temp / (MAXN + 1) * (MAXN + 1); up = temp / (MAXN + 1); ret.a[i + j] = temp1; } else {

up = 0;

ret.a[i + j] = temp; } }

if(up != 0)

ret.a[i + j] = up; }

ret.len = i + j;

while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--; return ret; }

BigNum BigNum::operator/(const int & b) const //′óêy??ò?????êy??DD?à3y???? {

BigNum ret; int i,down = 0;

for(i = len - 1 ; i >= 0 ; i--) {

ret.a[i] = (a[i] + down * (MAXN + 1)) / b;

down = a[i] + down * (MAXN + 1) - ret.a[i] * b; }

ret.len = len;

while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--; return ret; }

BigNum BigNum::operator*(const int &t) const //′óêy??ò?????êy??DD?à3y???? {

BigNum b(t); return *this*b; }

BigNum BigNum::operator+(const int &t) const //′óêy??ò?????êy??DD?à3y????

{

BigNum b(t); return *this + b; } int BigNum::operator %(const int & b) const //′óêy??ò???intààDíμ?±?á???DDè??￡???? {

int i,d=0;

for (i = len-1; i>=0; i--) {

d = ((d * (MAXN+1))% b + a[i])% b; }

return d; }

BigNum BigNum::operator^(const int & n) const {

BigNum t,ret(1); int i; if(n<0)

exit(-1); if(n==0)

return 1; if(n==1)

return *this; int m=n; while(m>1) {

t=*this;

for( i=1;i<<1<=m;i<<=1) {

t=t*t; } m-=i; ret=ret*t; if(m==1)

ret=ret*(*this); }

return ret; }

bool BigNum::operator>(const BigNum & T) const {

int ln;

if(len > T.len)

//′óêyμ?n′?·????? //′óêyoíáíò???′óêyμ?′óD?±è?? return true; else if(len == T.len) {

ln = len - 1;

while(a[ln] == T.a[ln] && ln >= 0) ln--;

if(ln >= 0 && a[ln] > T.a[ln]) return true; else

return false; } else

return false; }

bool BigNum::operator >(const int & t) const //′óêyoíò???intààDíμ?±?á?μ??àμè±è?? {

BigNum b(t); return *this>b; }

bool BigNum::operator==(const BigNum & T) const //′óêyoíáíò???′óêyμ?′óD?±è?? {

int ln;

if(len != T.len) return false; else {

ln = len - 1;

while(ln >= 0 && a[ln] == T.a[ln]) ln--; if(ln >= 0)

return false; else

return true; } }

bool BigNum::operator ==(const int & t) const //′óêyoíò???intààDíμ?±?á?μ??àμè±è?? {

BigNum b(t); return *this>b; }

void BigNum::print() {

int i;

cout << a[len - 1];

for(i = len - 2 ; i >= 0 ; i--) {

cout.width(DLEN); cout.fill('0'); cout << a[i]; }

cout << endl; } //′óêy?áê?

BigNum n; BigNum x; BigNum y; string s; int len;

BigNum fact(BigNum n) {

if (n == BigNum(1)) return BigNum(1); return n * fact(n - 1); }

BigNum toNum(string s) {

bool b[27];

BigNum ret = 0;

memset(b,1,sizeof(b)); for(int i = 0; i < len; i++) {

int sum = 0; b[s[i] - 'A'] = 0;

for(int j = 0; j < s[i] - 'A'; j++) {

sum += b[j]; }

ret = ret * (len - i) + sum; }

return ret; }

void toP(BigNum num) {

BigNum zz = fact(len); bool b[27]; int a[27];

for(int i = 0; i

a[len-i-1]=num%(i+1); num=num/(i+1); }

memset(b,1,sizeof(b));

for(int index = 0; index < len - 1; index++) {

int sum = -1; int j;

for(j = 0; sum < a[index]; j++) {

sum += b[j]; } j--; b[j]=0;

cout<<(char)('A'+j); }

int j = -1;

while(!b[++j]);

cout<<(char)('A' + j)<

int main() {

char nn[99]; bool flag;

BigNum temp; while(cin>>s>>nn) {

if(nn[0]=='-') {

flag=0;

n=BigNum(nn+1); } else {

flag=1;

n=BigNum(nn); }

len = s.size(); x = toNum(s);

if(flag && x+n > fact(len) - 1) {

cout<<\ }

else if(!flag && n > x) {

cout<<\ } else {

if(flag)

y = x + n; else

y = x - n; // y.print(); toP(y); } } }

I.散步

本题其实思路还是比较容易想出来的。“只有至少存在一条从B到终点的时间比从A到终点的所有路径所花费的时间更少时才可以从A到B”这句话的意思就是当且仅当B到终点的最短路径比A到终点更短的时候才会从A到B。所以先从魔法森林(n,m)开始一次BFS，求出所有点到终点的最短路径长度。需要注意的是路径计算是包括起点和终点的。然后从起点开始进行记忆化搜索每个点只遍历一次，找出从起点到终点一共有多少条路径。因为严格限制了移动方向是单向的，所以不存在环的情况。最后输出就可以了，需要注意的是存在到不了终点的情况。因为答案可能非常大，所以请用long long 或者int64存储。 #include #include #include using namespace std; int map[51][51],t[51][51]; long long s[51][51];

int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int n,m;

struct pp {

int x,y; };

queue que; int flag[99][99];

void bfs() {

pp a,b;

int dx,dy,i,spend; a.x=n-1;a.y=m-1;

t[n-1][m-1]=map[n-1][m-1]; que.push(a);

while(!que.empty()) {

b=que.front(); que.pop();

for(i=0;i<4;i++) {

dx=b.x+dir[i][0]; dy=b.y+dir[i][1];

if(dx>=0&&dx=0&&dy

spend=t[b.x][b.y]+map[dx][dy]; if(t[dx][dy]==-1||spend

a.x=dx; a.y=dy;

t[dx][dy]=spend; que.push(a); } } } } }

long long dfs(int x,int y) {

int i;

if(s[x][y]>-1)

return s[x][y]; if(x==n-1&&y==m-1) return 1; flag[x][y]++; s[x][y]=0;

for(i=0;i<4;i++) {

int xx=x+dir[i][0]; int yy=y+dir[i][1];

if(xx>=0&&xx=0&&yy

if(t[x][y]>t[xx][yy]) {

s[x][y]+=dfs(xx,yy); } } }

return s[x][y]; }

int main() {

int i,j;

while(cin>>n>>m) {

for(i=0;i

for(j=0;j

cin>>map[i][j];

t[i][j]=-1; }

while(!que.empty()) que.pop(); memset(s,-1,sizeof(s)); memset(flag,0,sizeof(flag)); bfs(); dfs(0,0);

cout<

return 0; }

J.IQ test?和K.IQ test 2

可以证明总是脸上数字最大的那个人最先猜到 证明：

加设这三个数是a,b,a+b

用1，2，3对这三个人编号 不妨设 a > b

设f（x，y）表示某人看到的两个数是x和y，他所能判断自己的数是什么至少经过的轮数 显然f(x,y) == f(y,x)

现在分别站在1，2，3角度来讨论这个问题 1需要f(b,a+b) 轮才能判断 2需要f(a,a+b) 轮才能判断 3要f(a,b)轮

现在3假设自己是a-b

那么在3的世界中的1会在第f(b,a-b)轮给出判断 在3的世界中的2会在第f(a,a-b)轮给出判断

所以3一定会在min(f(b,a-b),f(a,a-b))+1轮给出判断 可以得到f(a,b) == min(f(b,a-b),f(a,a-b))+1 所以

f(b,a+b) == min(f(a,b),f(a,a+b))+1 ............(1) f(a,a+b) == min(f(a,b),f(b,a+b))+1 ............(2) （1）代入（2）

f(a,a+b) == min( f(a,b), min(f(a,b) , f(a,a+b))+1 ) + 1 假设f(a,a+b) < f(a,b)

=》 f(a,a+b) == min(f(a,b),f(a,a+b)+1)+1 =》 f(a,a+b) == f(a,a+b)+2 矛盾 假设 f（a,a+b）== f(a,b)

=》 f(a,a+b) == min(f(a,b),f(a,a+b)+1) +1 =》 f(a,a+b) == f(a,b)+1 矛盾 所以f(a,a+b) >f(a,b) 成立 同理 f(b,a+b)>f(a,b) 证毕

那么比如2 3 5，最多3轮结束，因为脸上是5的人先假设自己脸上是1，他足够聪明，可以计算出如果是2 3 1那么在第二轮的时候脸上是3的人就会猜到自己是3，如果第二轮他没猜到那么他就能知道自己脸上一定不是1，所以，在第三轮的时候他一定能确定自己脸上的数。

#include using namespace std; #ifdef _WIN32

#define i64 __int64 #else

#define i64 long long #endif

i64 find(i64 x,i64 y) { if(x==0 || y==0 ) return 0; if(x

int main() { i64 a,b,c; while(cin>>a>>b>>c) { if(a==0 && b==0 && c==0) return 0; if(a>c) swap(a,c); if(b>c) swap(b,c); cout<

L.the end of the world

显然世界的结构是一棵树，关键是计算每条边正向和逆向的期望流量，可以使用树形dp， 选择一个根节点，s[x]表示x节点有多少边，go[x]表示从x节点出发往父节点走的流量， back[x]表示从x的父节点到它的流量，就是逆向流量。然后通过dfs1计算出父子关系，通过dfs2计算出go，通过dfs3计算出back，复杂度O（n）。

#include #include #include #include #include #include #include #include

int t[maxn]; bool vis[maxn]; void df1(int now) { int to; vis[now] = true; for(int i=0;i

t[to] = now; df1(to); } } return ; }

void df2(int now) { int to; if(t[now]!=-1) go[now]=1.0/s[now]; else go[now] = 0.0; sum[now]=0.0; for(int i=0;i

void df3(int now) { int to; for(int i=0;i

double start()

{ for(int i=1;i<=n;i++) { s[i] = g[i].size(); } t[1] = -1; memset(vis,false,sizeof(vis)); df1(1); df2(1); back[1]=0.0; df3(1); double re=0.0; if(g[1].size()==1) { re = go[g[1][0]]; } for(int i=2;i<=n;i++) { if(g[i].size()==1) { re = max(re,back[i]); } } return re; }

int main() { while(cin>>n) { if(!n) return 0; for(int i=0;i<=n;i++) g[i].clear(); int x,y; for(int i=1;i<=n-1;i++) { //cin>>x>>y; scanf(\ g[x].push_back(y); g[y].push_back(x); } printf(\ } return 0;

}

本文来源：https://www.bwwdw.com/article/x9yw.html