T1&＃xff1a;问题 A: 完全平方回文数

题目描述

    给定一个十进制自然数的范围和进制的范围&＃xff0c;十进制自然数范围在1~44700之间,进制的范围在2~36之间。给定范围里的数中,有些数的平方,在某进制下既是完全平方数又是回文数。本题的任务是统计给定范围内有多少个数的平方满足下列条件:仅在某一进制下既是完全平方数又是回文数。
    说明:32&＃61;9,因为它在十进制和十一进制中都是回文数,所以9不能算;同样, 262&＃61;676也不算。

输入

    一行四个整数,分别表示给定的十进制自然数的范围和进制的范围。

输出

    一行一个正整数,表示给定范围内满足条件的数的个数。

样例输入

1 100 9 11

样例输出

12

提示

【样例说明】

62&＃61;36&＃61;33 base 11

102&＃61; 100&＃61; 121 base9

112&＃61;121&＃61; 121 base 10

122&＃61; 144&＃61; 121 base 11

202 &＃61; 400 &＃61; 484 base 9

222&＃61; 484 &＃61; 484 base 10

242&＃61; 576 &＃61; 484 base 11

722&＃61; 5184 &＃61; 3993 base 11

822&＃61; 6724&＃61; 10201 base 9

842&＃61; 7056&＃61; 5335 base 11

912&＃61; 8281 &＃61; 12321 base 9

1002&＃61; 10000&＃61; 14641 base 9

题解

这是一道无脑的模拟题。只用枚举每一个数&＃xff0c;判断这个数在规定的所有进制中是回文数的个数&＃xff0c;如果个数为1&＃xff0c;表示可以ans&＃43;1&＃xff0c;否则枚举下一个数。转进制其实很简单&＃xff0c;想象一下一个很大的数5546435635664554&＃xff0c;把它转化成10进制是怎样做的&＃xff1f;

每一步模10再除以10&＃xff0c;就是4,5,5,4,6,6,5,3,6,5,3,4,6,4,5,5。然后倒过来就是这个数了。

如果是11进制呢&＃xff1f;那么就是模11再除以11.

也就是&＃xff1a;4,0,8,5,6,0,4,6,1,1,10,2,7,6,3,1.倒过来就是一个11进制的数了。注意&＃xff0c;这里的10表示的是数字&＃xff0c;一般在16进制中会用A来表示。

判断是不是回文数&＃xff0c;就看第i位数字与第n-i&＃43;1位数字是否都是相等。可以先用一个a数组存一下每位数字&＃xff0c;然后for循环判断即可。判断回文数的效率也是不可计算的&＃xff0c;平均下来大概是一个5左右的常数。

参考代码

#include
using namespace std;
int l,r,lowest,highest,ans&＃61;0,a[1000],len;
bool check(int p,int q)
{len&＃61;0;while(p){a[&＃43;&＃43;len]&＃61;p%q;p/&＃61;q;}for(int i&＃61;1;i<&＃61;len/2;i&＃43;&＃43;)if(a[i]!&＃61;a[len-i&＃43;1]) return false;return true;
}
int main()
{scanf("%d%d%d%d",&l,&r,&lowest,&highest);for(int i&＃61;l;i<&＃61;r;i&＃43;&＃43;){int num&＃61;0;for(int j&＃61;lowest;j<&＃61;highest;j&＃43;&＃43;){if(check(i*i,j)) num&＃43;&＃43;;if(num&＃61;&＃61;2) break;}if(num&＃61;&＃61;1) ans&＃43;&＃43;;}printf("%d",ans);return 0;
}

T2:问题 B: 均分纸牌

题目描述

    有n堆纸牌,编号分别为1&＃xff0c;2, ... ,n。每堆上有若干张,但纸牌总数必为n的倍数。可以在任一堆上取若干张纸牌,然后移动。
    移牌规则为:在编号为1的堆上取的纸牌,只能移到编号为2的堆上;在编号为n的堆上取的纸牌,只能移到编号为n-1的堆上;其他堆上取的纸牌,可以移到相邻左边或右边的堆上。
    现在要求找出一种移动方法,用最少的移动次数使每堆上纸牌数都一样多。
    例如n&＃61;4,4 堆纸牌数分别为:①9 ②8 ③17 ④6
    移动3次可达到目的:
    从③取4张牌放到④(9 8 13 10) -> 从③取3张牌放到②(9 11 10 10) -> 从②取1张牌放到①(10 10 10 10)。

输入

n(n堆纸牌,1 <&＃61;n<&＃61;100)
a1 a2 ... an (n堆纸牌,每堆纸牌初始数,I<&＃61;ai <&＃61; 10000)

输出

所有堆均达到相等时的最少移动次数。

样例输入

4

9 8 17 6

样例输出

3

题解

这道题是一个贪心。可以这样来想&＃xff1a;对于最左边的牌&＃xff0c;如果没有能达到平均数&＃xff0c;那么必然需要与它右边的牌进行交换&＃xff08;可能获得也可能舍去&＃xff09;&＃xff0c;因此只用记录正负即可。同样的&＃xff0c;这个操作能够使最左边的牌数达到平均数&＃xff08;如果第二堆不够可以先欠着&＃xff0c;或者说可以从大的牌堆开刀&＃xff09;。然后第二堆就变成了最左边的一堆了&＃xff0c;就接着进行以上操作。如果这个堆的牌数已经达到了平均数&＃xff0c;就跳过。如此就可以O(n)的完成本题。搜索的话可能会超时一些点。

参考代码

#include
using namespace std;
int n,a[200],sum&＃61;0,ans&＃61;0;
int main()
{scanf("%d",&n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) {scanf("%d",&a[i]);sum&＃43;&＃61;a[i]; }sum/&＃61;n;for(int i&＃61;1;i}

T3&＃xff1a;问题 C: 打击犯罪

题目描述

某个地区有 n(n<&＃61;1000)个犯罪团伙&＃xff0c;当地警方按照他们的危险程度由高到低给他们编号为 1-n&＃xff0c;他们有些团伙之间有直接联系&＃xff0c;但是任意两个团伙都可以通过直接或间接的方式联系&＃xff0c;这样这里就形成了一个庞大的犯罪集团&＃xff0c;犯罪集团的危险程度由集团内的犯罪团伙数量唯一确定&＃xff0c;而与单个犯罪团伙的危险程度无关&＃xff08;该犯罪集团的危险程度为 n&＃xff09;。现在当地警方希望花尽量少的时间&＃xff08;即打击掉尽量少的团伙&＃xff09;&＃xff0c;使得庞大的犯罪集团分离成若干个较小的集团&＃xff0c;并且他们中最大的一个的危险程度不超过 n/2。为达到最好的效果&＃xff0c;他们将按顺序打击掉编号 1 到 k 的犯罪团伙&＃xff0c;请编程求出 k 的最小值。

输入

第一行一个正整数 n。接下来的 n 行每行有若干个正整数&＃xff0c;第一个整数表示该行除第一个外还有多少个整数&＃xff0c;若第 i 行存在正整数 k&＃xff0c;表示 i&＃xff0c;k 两个团伙可以直接联系。

输出

一个正整数&＃xff0c;为 k 的最小值

样例输入

7

2 2 5

3 1 3 4

2 2 4

2 2 3

3 1 6 7

2 5 7

2 5 6

样例输出

1

提示

【提示】
输出 1&＃xff08;打击掉犯罪团伙&＃xff09;

题解

第一眼看到还以为是找割点&＃xff0c;结果想了半天才看到要按照顺序打击范围&＃xff08;-无语-&＃xff09;&＃xff0c;由于数据范围才1000&＃xff0c;直接O(n)枚举k&＃xff0c;然后对于每一种情况重新dfs计算连通块的大小&＃xff0c;知道第一个小于等于n/2就可以输出答案退出了。注意&＃xff0c;已经端掉的犯罪集团VIS应该定为0&＃xff0c;然后直接从i&＃43;1开始dfs每一块即可。

参考代码 

#include
using namespace std;
struct tree
{int nxt,to;
}tr[2001000];
int head[2001000],vis[2000],cnt&＃61;0,ans&＃61;0;
int n,m;
void build_tree(int u,int v)
{tr[&＃43;&＃43;cnt].nxt&＃61;head[u];tr[cnt].to&＃61;v;head[u]&＃61;cnt;
}
void dfs(int k)
{for(int i&＃61;head[k];i;i&＃61;tr[i].nxt){int to&＃61;tr[i].to;if(vis[to]) continue;vis[to]&＃61;1;ans&＃43;&＃43;;dfs(to);}
}
bool check(int k)
{for(int i&＃61;1;i<&＃61;k;i&＃43;&＃43;) vis[i]&＃61;1;for(int i&＃61;k&＃43;1;i<&＃61;n;i&＃43;&＃43;) vis[i]&＃61;0;for(int i&＃61;k&＃43;1;i<&＃61;n;i&＃43;&＃43;){if(vis[i]) continue;ans&＃61;1;vis[i]&＃61;1;dfs(i);if(ans>n/2) return false;}return true;
}
int main()
{scanf("%d",&n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%d",&m);for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){int v;scanf("%d",&v);build_tree(i,v);build_tree(v,i);}}int l&＃61;1,r&＃61;n;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(check(i)){printf("%d",i);return 0;}}printf("%d",l);return 0;
}

T4&＃xff1a;问题 D: 农场派对

题目描述

N(1≤N≤1000) 头牛要去参加一场在编号为 x(1≤x≤N)的牛的农场举行的派对。有 M(1≤M≤100000)条有向道路&＃xff0c;每条路长 Ti(1≤Ti≤100)&＃xff1b;每头牛都必须参加完派对后回到家&＃xff0c;每头牛都会选择最短路径。求这 N 头牛的最短路径&＃xff08;一个来回&＃xff09;中最长的一条的长度。 特别提醒&＃xff1a;可能有权值不同的重边。

输入

第 1 行&＃xff1a;3 个空格分开的整数 N,M,X&＃xff1b;
第 2…M 行&＃xff1a;3 个空格分开的整数 Ai,Bi,Ti &＃xff0c;表示有一条从 Ai 到 Bi 的路&＃xff0c;长度为 Ti 。

输出

一行一个数&＃xff0c;表示最长最短路的长度。

样例输入

4 8 2

1 2 4

1 3 2

1 4 7

2 1 1

2 3 5

3 1 2

3 4 4

4 2 3

样例输出

10

题解

由于一头牛从本家通向x&＃xff0c;走的是最短距离&＃xff0c;再从x回家&＃xff0c;走最短距离。因此可以想象都是由x出发&＃xff0c;建一个正图&＃xff0c;一个反图&＃xff0c;代表来回&＃xff0c;然后直接以x作为初始节点求一个单源最短路&＃xff0c;然后对于每一个非x的点&＃xff0c;求一下两个最小值的和&＃xff0c;然后取max就可以了。

参考代码

#include
#include
#include
using namespace std;
queueq;
int n,m,x;
struct tree
{int nxt,to,dis;
};
tree tr1[100100],tr2[100100];
int head1[100100],cnt1&＃61;0,vis1[2000],di1[2000],ans&＃61;0;
int head2[100100],cnt2&＃61;0,vis2[2000],di2[2000];
void build_tree(int u,int v,int d)
{tr1[&＃43;&＃43;cnt1].nxt&＃61;head1[u];tr1[cnt1].to&＃61;v;tr1[cnt1].dis&＃61;d;head1[u]&＃61;cnt1;tr2[&＃43;&＃43;cnt2].nxt&＃61;head2[v];tr2[cnt2].to&＃61;u;tr2[cnt2].dis&＃61;d;head2[v]&＃61;cnt2;
}
int main()
{memset(di1,127/3,sizeof(di1));memset(di2,127/3,sizeof(di2));scanf("%d%d%d",&n,&m,&x);while(m--){int u,v,d;scanf("%d%d%d",&u,&v,&d);build_tree(u,v,d);}q.push(x);vis1[x]&＃61;1;di1[x]&＃61;0;while(!q.empty()){int pt&＃61;q.front();q.pop();vis1[pt]&＃61;0;for(int i&＃61;head1[pt];i;i&＃61;tr1[i].nxt){int to&＃61;tr1[i].to,dis&＃61;tr1[i].dis;if(di1[to]>di1[pt]&＃43;dis){di1[to]&＃61;di1[pt]&＃43;dis;if(!vis1[to]){vis1[to]&＃61;1;q.push(to);}}}}q.push(x);vis2[x]&＃61;1;di2[x]&＃61;0;while(!q.empty()){int pt&＃61;q.front();q.pop();vis2[pt]&＃61;0;for(int i&＃61;head2[pt];i;i&＃61;tr2[i].nxt){int to&＃61;tr2[i].to,dis&＃61;tr2[i].dis;if(di2[to]>di2[pt]&＃43;dis){di2[to]&＃61;di2[pt]&＃43;dis;if(!vis2[to]){vis2[to]&＃61;1;q.push(to);}}}}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){if(i&＃61;&＃61;x) continue;if(di1[i]&＃43;di2[i]>ans) ans&＃61;di1[i]&＃43;di2[i];}printf("%d",ans);return 0;
}

T5&＃xff1a;问题 E: 树的统计

题目描述

一树上有 n 个节点&＃xff0c;编号分别为 1 到 n&＃xff0c;每个节点都有一个权值 w。我们将以下面的形式来要求你对这棵树完成一些操作&＃xff1a;
1. CHANGE u t &＃xff1a;把节点 u 权值改为 t&＃xff1b;
2. QMAX u v &＃xff1a;询问点 u 到点 v 路径上的节点的最大权值&＃xff1b;
3. QSUM u v &＃xff1a;询问点 u 到点 v 路径上的节点的权值和。
注意&＃xff1a;从点 u 到点 v 路径上的节点包括 u 和 v 本身。

输入

第一行为一个数 n&＃xff0c;表示节点个数&＃xff1b;
接下来 n-1 行&＃xff0c;每行两个整数 a,b&＃xff0c;表示节点 a 与节点 b 之间有一条边相连&＃xff1b;
接下来 n 行&＃xff0c;每行一个整数&＃xff0c;第 i 行的整数 wi 表示节点 i 的权值&＃xff1b;
接下来一行&＃xff0c;为一个整数 q &＃xff0c;表示操作总数&＃xff1b;
接下来 q 行&＃xff0c;每行一个操作&＃xff0c;以 CHANGE u t 或 QMAX u v 或 QSUM u v的形式给出。

输出

对于每个 QMAX 或 QSUM 的操作&＃xff0c;每行输出一个整数表示要求的结果。

样例输入

4

1 2

2 3

4 1

4 2 1 3

12

QMAX 3 4

QMAX 3 3

QMAX 3 2

QMAX 2 3

QSUM 3 4

QSUM 2 1

CHANGE 1 5

QMAX 3 4

CHANGE 3 6

QMAX 3 4

QMAX 2 4

QSUM 3 4

样例输出

4

1

2

2

10

6

5

6

5

16

提示

【数据范围与提示】

对于 100% 的数据&＃xff0c;有 1≤n≤3×104 ,0≤q≤2×105 。

中途操作中保证每个节点的权值 w 在 -30000 至 30000 之间。

题解

树链剖分板题有没有&＃xff1f;这里就是一个。写一个能单点修改、查询区间最值、查询区间和的线段树&＃xff0c;然后写一个树链剖分进行更改即可。如果不知何为“线段树”、何为“树链剖分”&＃xff0c;可查查百度。&＃xff08;特别注意&＃xff1a;debug了一个小时&＃xff0c;结果是top[x]!&＃61;top[y]我把while写成了if&＃xff0c;导致样例能对&＃xff0c;但是只能过20分&＃xff0c;特别要小心&＃xff01;&＃xff01;&＃xff09;

参考代码

#include
#define lc (x<<1)
#define rc (x<<1|1)
#define MAXN 100001
#define LL long long
using namespace std;
struct tree1
{int nxt,to;
}tr[MAXN*2];
struct tree2
{int l,r;LL sum,mx;
}ask[MAXN*4];
char s[200];
LL a[MAXN];
int head[MAXN*2],cnt&＃61;0,tot&＃61;0,n,m;
int son[MAXN],fa[MAXN],dep[MAXN],size[MAXN];
int seg[MAXN],rev[MAXN],top[MAXN];
LL max1(LL p,LL q) { return p>q?p:q; }
int swap1(int & p,int & q)
{ int c&＃61;p;p&＃61;q;q&＃61;c; }
void make_tree(int x,int l,int r)
{ask[x].l&＃61;l;ask[x].r&＃61;r;if(l&＃61;&＃61;r){ask[x].mx&＃61;ask[x].sum&＃61;a[rev[l]];return;}int mid&＃61;(l&＃43;r)/2;make_tree(lc,l,mid);make_tree(rc,mid&＃43;1,r);ask[x].sum&＃61;ask[lc].sum&＃43;ask[rc].sum;ask[x].mx&＃61;max1(ask[lc].mx,ask[rc].mx);
}
void update(int x,int pos,LL k)
{if(ask[x].l&＃61;&＃61;ask[x].r){ask[x].mx&＃61;ask[x].sum&＃61;k;return ;}int mid&＃61;(ask[x].l&＃43;ask[x].r)/2;if(pos<&＃61;mid) update(lc,pos,k);else update(rc,pos,k);ask[x].sum&＃61;ask[lc].sum&＃43;ask[rc].sum;ask[x].mx&＃61;max1(ask[lc].mx,ask[rc].mx);
}
LL query_sum(int x,int l,int r)
{if(ask[x].l>r||ask[x].r&＃61;l&&ask[x].r<&＃61;r) return ask[x].sum;return query_sum(lc,l,r)&＃43;query_sum(rc,l,r);
}
LL query_max(int x,int l,int r)
{if(ask[x].l>r||ask[x].r&＃61;l&&ask[x].r<&＃61;r) return ask[x].mx;return max1(query_max(lc,l,r),query_max(rc,l,r));
}
void build_tree(int u,int v)
{tr[&＃43;&＃43;cnt].nxt&＃61;head[u];tr[cnt].to&＃61;v;head[u]&＃61;cnt;
}
void dfs1(int k,int f)
{size[k]&＃61;1;for(int i&＃61;head[k];i;i&＃61;tr[i].nxt){int to&＃61;tr[i].to;if(to&＃61;&＃61;f) continue;fa[to]&＃61;k;dep[to]&＃61;dep[k]&＃43;1;dfs1(to,k);size[k]&＃43;&＃61;size[to];if(size[to]>size[son[k]])son[k]&＃61;to;}
}
void dfs2(int k,int f)
{seg[k]&＃61;&＃43;&＃43;tot;rev[tot]&＃61;k;if(son[k]){top[son[k]]&＃61;top[k];dfs2(son[k],k);}for(int i&＃61;head[k];i;i&＃61;tr[i].nxt){int to&＃61;tr[i].to;if(to&＃61;&＃61;f) continue;if(top[to]&＃61;&＃61;0){top[to]&＃61;to;dfs2(to,k); } }
}
LL ask_sum(int x,int y)
{LL ans&＃61;0;while(top[x]!&＃61;top[y]){if(dep[top[x]]dep[y]) swap1(x,y);ans&＃43;&＃61;query_sum(1,seg[x],seg[y]);return ans;
}
LL ask_max(int x,int y)
{LL maxn&＃61;1ll<<63;while(top[x]!&＃61;top[y]){if(dep[top[x]]dep[y]) swap1(x,y);maxn&＃61;max1(maxn,query_max(1,seg[x],seg[y]));return maxn;
}
int main()
{scanf("%d",&n);for(int i&＃61;1;i}