ZCMU训练--190705：2016大学生程序设计比赛
目录
A:HDU 5933
B:HDU 5934
C:HDU 5935
D:HDU 6312
E:HDU 6308
F: HDU 5938
G:HDU 5606
H:HDU 1404
I:HDU 5358
J:HDU 1097
K:HDU 5943
A ：ArcSoft's Office Rearrangement
题目：
ArcSoft, Inc. is a leading global professional computer photography and computer vision technology company.
There are NN working blocks in ArcSoft company, which form a straight line. The CEO of ArcSoft thinks that every block should have equal number of employees, so he wants to re-arrange the current blocks into KK new blocks by the following two operations:
- merge two neighbor blocks into a new block, and the new block's size is the sum of two old blocks'.
- split one block into two new blocks, and you can assign the size of each block, but the sum should be equal to the old block.
Now the CEO wants to know the minimum operations to re-arrange current blocks into KK block with equal size, please help him.
Input
First line contains an integer TT, which indicates the number of test cases.
Every test case begins with one line which two integers NN and KK, which is the number of old blocks and new blocks.
The second line contains NN numbers a1a1, a2a2, ⋯⋯, aNaN, indicating the size of current blocks.
Limits
1≤T≤1001≤T≤100
1≤N≤1051≤N≤105
1≤K≤1051≤K≤105
1≤ai≤1051≤ai≤105
Output
For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the minimum operations.
If the CEO can't re-arrange KK new blocks with equal size, y equals -1.
Sample Input
3
1 3
14
3 1
2 3 4
3 6
1 2 3
Sample Output
Case #1: -1
Case #2: 2
Case #3: 3
题意：
某公司有 n 个工作区，这 n 个工作区依次分布在一条直线上。现在这个公司的老大 想要重新整治一下工作区，将原有的工作区分成 k 个工作区并且要求每个工作区当中的人数 相同。问最少操作次数是几次？ 操作有两种，操作一：将两个相邻工作区合并成一个新的工作区，新的工作区工作人员数等 于两个工作区的工作人员数的和；操作二：将一个工作区拆分成两个工作区，拆分成的两个 工作区的人数和等于原工作区人数。
思路：
人数不为 k 的整数倍一定不行，人数为 k 的整数倍一定可以。因为只能相邻两个工作 区进行合并，所以考虑顺序遍历贪心。每次对当前格进行拆分，多余的向后合并，注意如果 当前格是整数倍可以少进行一次拆分。
题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,a[100010];
int main(){
int T;
scanf( "%d" , &T );
for( int cas=1 ; cas<=T ; cas++ ){
scanf( "%lld%lld" , &n , &k );
ll sum=0;
for( int i=1 ; i<=n ; i++ ){
scanf( "%lld" , &a[i] );
sum=sum+a[i];
}
if( sum%k==0 ){
ll ans=0,ave=sum/k;
for( int i=1 ; i<=n ; i++ ){
if( a[i]%ave==0 ){
ans += a[i]/ave-1;
}else{
ans += a[i]/ave+1;
}
a[i+1] += a[i]%ave;
}
printf( "Case #%d: %lld\n" , cas , ans );
}else{
printf( "Case #%d: -1\n" , cas );
}
}
return 0;
}
我参考的博客：
1.https://blog.csdn.net/yu121380/article/details/77473358(和平均数比较）
2.https://blog.csdn.net/qq_36651153/article/details/77169824(从左向右贪心)
3.https://www.cnblogs.com/Coolxxx/p/6011351.html
(无解的情况是N个区间的总大小s mod M ! = 0, 其实题目就是给你一个总长位s的N个区间，要求你合并相邻的两个或拆开一个大区间，使得最后的每个区间大小都为s/M。那么如果原先的分界线和最终的分界线相同，那么就不必对这个分界线进行合并。有解的时候可以知道每个新区间的大小x，所以只要看Ai的前缀和里是否有x的倍数，如果有则这个位置不用操作。总共需要合并N-1次，拆分M-1次，扣掉不需要的操作t*2次，即为答案。)
4.https://blog.csdn.net/huatian5/article/details/52967458(思维题)
我的代码：（切记long long )
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<stdlib.h>
#define ll long long
using namespace std;
const double eps=1e-7;
const int maxn=300050;
ll y[maxn],x[maxn];
int main(){
int t;
int a,b;
int count=0;
scanf("%d",&t);
while(t--){
scanf("%d%d",&a,&b);
ll sum=0;
for(int i=1;i<=a;i++){
scanf("%d",&y[i]);
x[i]=x[i-1]+y[i];
sum+=y[i];
}
if(sum%b)printf("Case #%d: -1\n",++count);
else {
ll cnt=0;ll avg=sum/b;
for(int i=1;i<a;i++)
{
if(x[i]%avg==0)
cnt++;
}
ll step=a-1+b-1-2*cnt;
printf("Case #%d: %lld\n",++count,step);
}
}
return 0;
}
B - Bomb(有向图)
原题地址：http://acm.hdu.edu.cn/showproblem.php?pid=5934（hdu5934）
There are NN bombs needing exploding.
Each bomb has three attributes: exploding radius riri, position (xi,yi)(xi,yi) and lighting-cost cici which means you need to pay cici cost making it explode.
If a un-lighting bomb is in or on the border the exploding area of another exploding one, the un-lighting bomb also will explode.
Now you know the attributes of all bombs, please use the minimum cost to explode all bombs.
Input
First line contains an integer TT, which indicates the number of test cases.
Every test case begins with an integers NN, which indicates the numbers of bombs.
In the following NN lines, the ith line contains four intergers xixi, yiyi, riri and cici, indicating the coordinate of ith bomb is (xi,yi)(xi,yi), exploding radius is riri and lighting-cost is cici.
Limits
- 1≤T≤201≤T≤20
- 1≤N≤10001≤N≤1000
- −108≤xi,yi,ri≤108−108≤xi,yi,ri≤108
- 1≤ci≤1041≤ci≤104
Output
For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the minimum cost.
Sample Input
1
5
0 0 1 5
1 1 1 6
0 1 1 7
3 0 2 10
5 0 1 4
Sample Output
Case #1: 15
题意:
有 n 个炸弹，每个炸弹具有三个属性值：坐标（x,y）引爆半径 r 以及引爆成本 c。
当 引爆一枚炸弹时，这枚炸弹会同时引爆其爆炸半径内的所有炸弹。比如：炸弹 A 可以引爆 炸弹 B，炸弹 B 可以引爆炸弹 C，那么如果你引爆炸弹 A 即可引爆炸弹 A,B,C。问引爆所有 炸弹的最小成本。思路：
如果炸弹 A 可以引爆炸弹 B，则从炸弹 A 向炸弹 B 画一条连线，整个炸弹图将会变成 一个有向图。对于有向图只要引爆那些入度为 0 的点就可以将整个炸弹图全部引爆，也就是 最小成本。但是有一种情况是需要特殊处理的，有向图成环了。下面这种情况看似没有任何 一个入度为 0 的点，但是需要引爆环中任意一点才可以引爆所有炸弹。最终的结论就是：对 有向图进行强连通分量缩点，缩点后将所有入度为 0 的点成本相加。
![tps:https://img.haomeiwen.com/i16020496/decea51748505d81.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int n;
struct point{
ll x,y,r,c;
}p[1010];
int tol,head[1010];
struct edge{
int to,next;
}es[1000010];
void init(){
tol = 0; memset( head , -1 , sizeof(head) );
}
void addedge( int u , int v ){
es[tol].to = v;
es[tol].next = head[u];
head[u] = tol++;
}
bool ok( int a , int b ){
ll dx = p[a].x-p[b].x;
ll dy = p[a].y-p[b].y;
ll dd = p[a].r*p[a].r;
if( dx*dx+dy*dy<=dd ) return true;
else return false;
}
int low[1010],dfn[1010],Stack[1010],belong[1010],num[1010],pri[1010],indeg[1010];
int index,top,scc;
bool instack[1010];
void dfs( int u ){
int v;
low[u] = dfn[u] = ++index;
Stack[top++] = u;
instack[u] = true;
for( int i=head[u] ; i!=-1 ; i=es[i].next ){
v = es[i].to;
if( !dfn[v] ){
dfs( v );
if( low[u]>low[v] ) low[u] = low[v];
}else if( instack[v]&&low[u]>dfn[v] ){
low[u] = dfn[v];
}
}
if( low[u]==dfn[u] ){
scc++;
do{
v = Stack[--top];
instack[v] = false;
belong[v] = scc;
num[scc]++;
pri[scc] = min( pri[scc] , (int)p[v].c );
}while( v!=u );
}
}
void tarjan( int n ){
memset( dfn , 0 , sizeof(dfn) );
memset( instack , false , sizeof(instack) );
memset( num , 0 , sizeof(num) );
memset( pri , inf , sizeof(pri) );
memset( indeg , 0 , sizeof(indeg) );
index = scc = top = 0;
for( int i=1 ; i<=n ; i++ ){
if( !dfn[i] ) dfs(i);
}
}
int main(){
int T;
scanf( "%d" , &T );
for( int cas=1 ; cas<=T ; cas++ ){
scanf( "%d" , &n );
for( int i=1 ; i<=n ; i++ ){
scanf( "%lld%lld%lld%lld" , &p[i].x , &p[i].y , &p[i].r , &p[i].c );
}
init();
for( int i=1 ; i<=n ; i++ ){
for( int j=1 ; j<=n ; j++ ){
if( i==j ) continue;
if( ok( i , j ) ) addedge( i , j );
}
}
tarjan( n );
for( int u=1 ; u<=n ; u++ ){
for( int i=head[u] ; i!=-1 ; i=es[i].next ){
int v = es[i].to;
if( belong[u]==belong[v] ) continue;
indeg[belong[v]]++;
}
}
int ans = 0;
for( int i=1 ; i<=scc ; i++ ){
if( indeg[i]==0 ) ans += pri[i];
}
printf( "Case #%d: %d\n" , cas , ans );
}
return 0;
}
C - Car
Ruins is driving a car to participating in a programming contest. As on a very tight schedule, he will drive the car without any slow down, so the speed of the car is non-decrease real number.
Of course, his speeding caught the attention of the traffic police. Police record NN positions of Ruins without time mark, the only thing they know is every position is recorded at an integer time point and Ruins started at 00.
Now they want to know the minimum time that Ruins used to pass the last position.
Input
First line contains an integer TT, which indicates the number of test cases.
Every test case begins with an integers NN, which is the number of the recorded positions.
The second line contains NN numbers a1a1, a2a2, ⋯⋯, aNaN, indicating the recorded positions.
Limits
1≤T≤1001≤T≤100
1≤N≤1051≤N≤105
0<ai≤1090<ai≤109
ai<ai+1ai<ai+1
Output
For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the minimum time.
Sample Input
1
3
6 11 21
Sample Output
Case #1: 4
题意：
有一辆无敌拉风的驾驶汽车，只能匀速或者加速。因为这个拉风的特性，这辆驾驶汽 车成功的引起了交警的注意，被记录下 n 个时间整点的位置数据（位置数据是实数）。交警 还知道开着这辆汽车的是个飙车狂，喜欢极致快速。现在交警想要知道这个飙车狂花了多少 时间从位置 0 开始经过这 n 个点。即：问从 0 开始不减速到达最后一个点的最短时间。
思路：
由于不能减速，所以从最后一个点开始往前走。最后一段距离，一定是只花了一秒钟， 依次从后往前推算即可。
题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-8;
int n; double a[100010];
int main(){
int T;
scanf( "%d" , &T );
for( int cas=1 ; cas<=T ; cas++ ){a
scanf( "%d" , &n );
a[0] = 0;
for( int i=1 ; i<=n ; i++ ){
scanf( "%lf" , &a[i] );
}
for( int i=n ; i>=1 ; i-- ){
a[i] = a[i]-a[i-1];
}
ll ans = 1,tmp; double v = a[n];
for( int i=n-1 ; i>=1 ; i-- ){
tmp = ceil(a[i]/v-eps);
ans += tmp;
v = a[i]/tmp;
}
printf( "Case #%d: %lld\n" , cas , ans );
}
return 0;
}
我参考的博客：
1.https://blog.csdn.net/EventQueue/article/details/52995941(贪心策略，倒着看，从后往前，后面的速度尽可能的大，这样才能保证总的时间最短)
2.https://blog.csdn.net/mengxiang000000/article/details/52965196
3.https://blog.csdn.net/mrlry/article/details/53046532
4.https://www.cnblogs.com/Coolxxx/p/6011409.html (首先可以知道答案必为整数，并且每一段距离都是匀速的。从后往前看，最后一段距离X[N]-X[N-1]必然花了t=1s的时间（没有约束条件，速度可以任意加），V=X[N]-X[N-1]。那么在它之前的距离X‘，只要满足速度V‘<V即可，那么把X’均分成t段，每段时间为1，行走距离V‘，只要V’*t恰好>X‘即可。这样往前递推，每一段的速度都不能超过前面。注意精度问题 。)
5.https://blog.csdn.net/qingshui23/article/details/52973229
我的代码：
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<stdlib.h>
#define ll __int64
using namespace std;
const double eps=1e-7;
const int maxn=300050;
ll a[maxn];
void swap(int a,int b){
int temp;
temp=a;
a=b;
b=temp;
}
int main(){
int n,t;
int count=0;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
a[0]=0;
for(int i=1;i<=n;i++)
scanf("%I64d",&a[i]);
ll sum=0;
ll fenzi,fenmu;
for(int i=n;i>=1;i--)
{
if(i==n)
{
sum++;
fenzi=a[i]-a[i-1];
fenmu=1;
}
else
{
ll dis=a[i]-a[i-1];
fenmu*=dis;
swap(fenzi,fenmu);
ll tmpp=fenzi/fenmu+1;
if(fenzi%fenmu==0)tmpp--;
sum+=tmpp;
fenzi=dis;
fenmu=tmpp;
}
}
printf("Case #%d: ",++count);
printf("%I64d\n",sum);
}
return 0;
}
D - Game(签到题)
Alice and Bob are playing a game.
The game is played on a set of positive integers from 1 to n.
In one step, the player can choose a positive integer from the set, and erase all of its divisors from the set. If a divisor doesn't exist it will be ignored.
Alice and Bob choose in turn, the one who cannot choose (current set is empty) loses.
Alice goes first, she wanna know whether she can win. Please judge by outputing 'Yes' or 'No'.
Input
There might be multiple test cases, no more than 10. You need to read till the end of input.
For each test case, a line containing an integer n. (1≤n≤5001≤n≤500)
Output
A line for each test case, 'Yes' or 'No'.
Sample Input
1
Sample Output
Yes
题意：
博弈界忠实老玩家 Alice 和 Bob 又发明了一款新的博弈游戏。这个游戏是这个样子的 有一个集合集合内有 n 个数依次为 1，2，3，。。。，n。每个玩家每次可以从集合中选一个数 字，同时将集合内该数的所有因子删除。老规矩最后不能操作的玩家败北。由于 Alice 和 Bob 博弈游戏玩多了所以这次 Alice 和 Bob 打算当一次云玩家，只 BB 游戏的输赢自己不玩。问 给定 n 如果先手赢输出 Yes 先手败输出 No。
思路：
1 这个数字很特别它是所有数字的因子，你选那个数字这个一定会被删除。在 2,3,4,…,n 内选一个数字和在 1,2,3,…,n 内选一个 2 到 n 的数字这个游戏是一毛一样的。如果 2,3,4,…,n 这个游戏先手能玩赢，那么在 2,3,4,…,n 内选一个数字即可。如果 2,3,4,…,n 这个游 戏先手赢不了，那选个 1 把这个臭垃圾给对手吃。反正先手必赢（摊手。
AC代码：
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<stdlib.h>
#define ll __int64
using namespace std;
const double eps=1e-7;
const int maxn=300050;
char gd[6];
int main(){
int t, h, m;
vector<int>q;
while(cin>>t)
{
printf("Yes\n");
}
return 0;
}
E - Time Zone
Chiaki often participates in international competitive programming contests. The time zone becomes a big problem.
Given a time in Beijing time (UTC +8), Chiaki would like to know the time in another time zone ss.
Input
There are multiple test cases. The first line of input contains an integer TT (1≤T≤1061≤T≤106), indicating the number of test cases. For each test case:
The first line contains two integers aa, bb (0≤a≤23,0≤b≤590≤a≤23,0≤b≤59) and a string ss in the format of "UTC+X'', "UTC-X'', "UTC+X.Y'', or "UTC-X.Y'' (0≤X,X.Y≤14,0≤Y≤90≤X,X.Y≤14,0≤Y≤9).
Output
For each test, output the time in the format of hh:mmhh:mm (24-hour clock).
Sample Input
3
11 11 UTC+8
11 12 UTC+9
11 23 UTC+0
Sample Output
11:11
12:12
03:23
题意：
有一个中国的大老板经常全球各地跑，每次去别的国家他都要重新调整他手上那闪闪 发光的劳力士手表上的时间，他那枯燥且乏味的生活因此也变得如此生动。于是乎他找到了 你并示意了一下他手中的劳力士手表想要你帮他的劳力士手表编个程序，方便他每次出国调 整手表上的时间。即给定北京时间（东八区时间）求目标 X.Y 时区的时间。
思路：
模拟计算时区，但是听说先将时间调整到零时区会更好做。
题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
for( int T ; scanf( "%d" , &T )==1 ; ){
while( T-- ){
int a,b;
scanf( "%d%d" , &a , &b );
char s[25];
scanf( "%s" , s );
int x = 0,y = 0;
int len = strlen(s);
if( s[len-2]=='.' )
y = y*10+s[len-1]-'0';
for( int i=4 ; i<len&&s[i]!='.' ; i++ )
x = x*10+s[i]-'0';
a -= 8; y = y*6;
if( s[3]=='+' ) a += x,b += y;
else a -= x,b -= y;
if( b<0 ) a--,b += 60;
if( b>=60 ) a++,b -= 60;
if( a>=24 ) a -= 24;
if( a<0 ) a += 24;
printf( "%02d:%02d\n" , a , b );
}
}
return 0;
}
我参考的博客：https://www.cnblogs.com/lesroad/p/9367963.html
放上大佬的代码来对比：
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<stdlib.h>
#define ll __int64
using namespace std;
const double eps=1e-7;
const int maxn=300050;
char gd[6];
int main(){
int t, h, m;
char s[10];
cin>>t;
while(t--)
{
scanf("%d%d%s", &h, &m, s);
h = h*60+m;
int op = s[3]=='+'?1:-1;
double x;
sscanf(s+4, "%lf", &x);
x = (int)(x*10+0.005);
int cha = x*6*op-8*60;
h = (h+cha)%(24*60);
if(h < 0) h += 24*60;
printf("%02d:%02d\n", h/60, h%60);
}
return 0;
}
F - Four Operations
Little Ruins is a studious boy, recently he learned the four operations!
Now he want to use four operations to generate a number, he takes a string which only contains digits '1' - '9', and split it into 55 intervals and add the four operations '+', '-', '*' and '/' in order, then calculate the result(/ used as integer division).
Now please help him to get the largest result.
Input
First line contains an integer TT, which indicates the number of test cases.
Every test contains one line with a string only contains digits '1'- '9'.
Limits
1≤T≤1051≤T≤105
5≤length of string≤205≤length of string≤20
Output
For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result.
Sample Input
1
12345
Sample Output
Case #1: 1
题意：
经过时间的推移，90 后常做的口算本日益的变态了起来到了, 00 后这一代这个口算本 已经不是人能做的了，这件事情灰太狼非常有发言权。小灰灰这个 00 后开始小学了，每天 都有写不完的作业和写不完的变态口算本，都把小灰灰写哭了。灰太狼心想这口算本有这么 变态吗，于是拿起一看上面这么写着：1 秒时间限制做 100000 到以下口算题。每道口算题 的规格是这样子的，给一串数字要求在里面依次插入+，-，*，/变成一个表达式，求表达式 的最大值。灰太狼一筹莫展于是乎找到了你，求你这个编程大佬写个程序帮忙解决这个问题。
题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int T;
scanf( "%d" , &T );
for( int cas=1 ; cas<=T ; cas++ ){
char s[25]; scanf( "%s" , s );
ll ans = -10000; int len = strlen(s);
for( int i=1 ; i<=3&&i+4<=len ; i++ ){
ll a=0,b=0,c=0,d=0,e=0;
for( int j=0 ; j<len-i-3 ; j++ )
a = a*10+s[j]-'0';
for( int j=len-i-3 ; j<len-i-2 ; j++ )
b = b*10+s[j]-'0';
for( int j=len-i-2 ; j<len-i-1 ; j++ )
c = c*10+s[j]-'0';
for( int j=len-i-1 ; j<len-i ; j++ )
d = d*10+s[j]-'0';
for( int j=len-i ; j<len ; j++ )
e = e*10+s[j]-'0';
ans = max( ans , a+b-c*d/e );
}
for( int i=1 ; i<=3&&i+4<=len ; i++ ){
ll a=0,b=0,c=0,d=0,e=0;
for( int j=0 ; j<1 ; j++ )
a = a*10+s[j]-'0';
for( int j=1 ; j<len-i-2 ; j++ )
b = b*10+s[j]-'0';
for( int j=len-i-2 ; j<len-i-1 ; j++ )
c = c*10+s[j]-'0';
for( int j=len-i-1 ; j<len-i ; j++ )
d = d*10+s[j]-'0';
for( int j=len-i ; j<len ; j++ )
e = e*10+s[j]-'0';
ans = max( ans , a+b-c*d/e );
}
printf( "Case #%d: %lld\n" , cas , ans );
}
return 0;
}
思路：
先观察一下运算符号的顺序，再脑补一下怎样才可以使答案尽量最大化。然后很温馨
的献上一组测试数据 111991。
参考博客：https://www.cnblogs.com/Simon-X/p/6040672.html（一个只有5个部分，可以写成A+B-C*D/E，要使结果最大，则A+B最大，C*D/E最小，A+B最大，加号要么在第一位数后面，要么在最后一位数前面。C*D/E最小，C和D都是1位数，E只有可能是1~3位数，到3位数的时候已经为0了。所以最多只要就算三次即可，注意初始化。）
其他参考博客：https://www.cnblogs.com/Roni-i/p/7505345.html
https://blog.csdn.net/u010568270/article/details/52965718
大佬的解题方法的对比：（反正我是看不懂了）
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<stdlib.h>
#define ll __int64
using namespace std;
const double eps=1e-7;
const int maxn=300050;
char a[25];
int main(){
int n;
int T,len,i,j;
ll sum,l,r,L,L10,R,R10;
scanf("%d",&T);
int count=0;
while(T--){
a[0]=0;
scanf("%s",a);
sum=(ll)1<<63;//
len=strlen(a);
//
L=0,L10=1;
for(int i=0;i<len-3;++i,L10*=10)
L=L*10+a[i]-'0';
L10/=10;
//
R=0;R10=1;
j=min(3,len-4);
for(int i=1;i<=j;++i){
R=(a[len-i]-'0')*R10+R;
R10*=10;
l=max(L/L10+L%L10, L/10+L%10);
L10/=10;L/=10;
r=(a[len-i-2]-'0')*(a[len-i-1]-'0')/R;
sum=max(sum,l-r);
}
printf("Case #%d: ",++count);
printf("%I64d\n",sum);
}
return 0;
}
G - tree
There is a tree(the tree is a connected graph which contains nn points and n−1n−1 edges),the points are labeled from 1 to nn,which edge has a weight from 0 to 1,for every point i∈[1,n]i∈[1,n],you should find the number of the points which are closest to it,the clostest points can contain ii itself.
Input
the first line contains a number T,means T test cases.
for each test case,the first line is a nubmer nn,means the number of the points,next n-1 lines,each line contains three numbers u,v,wu,v,w,which shows an edge and its weight.
T≤50,n≤105,u,v∈[1,n],w∈[0,1]T≤50,n≤105,u,v∈[1,n],w∈[0,1]
Output
for each test case,you need to print the answer to each point.
in consideration of the large output,imagine ansiansi is the answer to point ii,you only need to output,ans1 xor ans2 xor ans3.. ansnans1 xor ans2 xor ans3.. ansn.
Sample Input
1
3
1 2 0
2 3 1
Sample Output
1
in the sample.
,so you need to output 1.
题意：
蚂蚁森林在阿拉赞种了好多树，所以我们也做一个树的题应应景。题目是这样的：一 颗树有 n 个点 n-1 条边，n-1 条边中每条边的边权不是 0 就是 1。求距离各个点的距离 0 的 点数异或和。
思路：
这题是明则考树，暗则考并查集。边权为 0 的边做并查集揉作一团。
题解
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int Size=100010;
int pre[Size];
int num[Size];
int Find(int x){
if(x!=pre[x]) pre[x]=Find(pre[x]);
return pre[x];
}
void mix(int x,int y){
int fx=Find(x);
int fy=Find(y);
if(fx!=fy){
pre[fy]=fx;
num[fx]+=num[fy];
}
}
int main(){
int t,i,n,u,v,w;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=1;i<=n;i++) pre[i]=i,num[i]=1;
for(i=1;i<n;i++){
scanf("%d%d%d",&u,&v,&w);
if(w==0) mix(u,v);
}
int ans=0;
for(i=1;i<=n;i++) if(i==Find(i)&&num[i]%2) ans^=num[i];
printf("%d\n",ans);
}
return 0;
}
H - Digital Deletions
<dd style="box-shadow: rgb(136, 136, 136) 3px 3px 6px; background-color: rgba(210, 210, 255, 0.5); padding: 20px; border-radius: 10px; font-family: Merriweather, serif; font-size: 18px; -webkit-font-smoothing: antialiased; color: rgb(0, 0, 0); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">
Digital deletions is a two-player game. The rule of the game is as following.
Begin by writing down a string of digits (numbers) that's as long or as short as you like. The digits can be 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 and appear in any combinations that you like. You don't have to use them all. Here is an example:
On a turn a player may either:
Change any one of the digits to a value less than the number that it is. (No negative numbers are allowed.) For example, you could change a 5 into a 4, 3, 2, 1, or 0.
Erase a zero and all the digits to the right of it.
The player who removes the last digit wins.
The game that begins with the string of numbers above could proceed like this:
Now, given a initial string, try to determine can the first player win if the two players play optimally both.
<dt style="font-weight: bold; margin-top: 20px; padding-left: 35px; color: rgb(0, 0, 0); font-family: 楷体; font-size: medium; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">Input</dt>
The input consists of several test cases. For each case, there is a string in one line.
The length of string will be in the range of [1,6]. The string contains only digit characters.
Proceed to the end of file.
Output
Output Yes in a line if the first player can win the game, otherwise output No.
Sample Input
0
00
1
20
Sample Output
Yes
Yes
No
No
题意；
博弈老玩家+博弈云玩家 Alice 和 Bob 又回来了。她（他）们还带回来了一款新游戏， 名日数字删除。这个游戏是在数字串上进行的，每次玩家都可以选择任意位置上的数字。如 果该位置上的数字为 0 则删除该数以及该数后面的所有数字，若为非 0 则可以减小这个数字 比如数字 5 可以减小为 4，3，2，1，0。Alice 和 Bob 这两个博弈老玩家又摆出一副牛逼哄 哄的样子，吵着闹着要做云玩家，忘了说这个游戏也是不能操作的玩家算输。
题意：
对于首位为 0 的先手秒赢，其他情况 SG 函数暴力跑一跑。
题解：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
const int Size=1000010;
int SG[Size];
void init(){
memset(SG,0,sizeof(SG));
int i,j,t; SG[0]=1;
for(i=1;i<1000000;i++){
int temp=i,p=1;
while(temp){
t=temp%10;
if(t==0){
if(SG[temp/10]==0) SG[i]=1;
}else{
if(temp<10){
for(j=1;j<t;j++){
if(SG[i-j*p]==0) SG[i]=1;
}
}else{
for(j=1;j<=t;j++){
if(SG[i-j*p]==0) SG[i]=1;
}
}
}
temp/=10,p*=10;
}
}
}
int main(){
init();
char in[10];
while(scanf("%s",in)!=EOF){
if(in[0]=='0'){
printf("Yes\n");
}else{
int temp=0,i;
for(i=0;in[i]!='\0';i++) temp=temp*10+in[i]-'0';
if(SG[temp]) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
I - First One
soda has an integer array a1,a2,…,ana1,a2,…,an. Let S(i,j)S(i,j) be the sum of ai,ai+1,…,ajai,ai+1,…,aj. Now soda wants to know the value below:
∑i=1n∑j=in(⌊log2S(i,j)⌋+1)×(i+j)
∑i=1n∑j=in(⌊log2S(i,j)⌋+1)×(i+j)
Note: In this problem, you can consider log20log20 as 0.
Input
There are multiple test cases. The first line of input contains an integer TT, indicating the number of test cases. For each test case:
The first line contains an integer nn (1≤n≤105)(1≤n≤105), the number of integers in the array.
The next line contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤105)(0≤ai≤105).
Output
For each test case, output the value.
Sample Input
1
2
1 1
Sample Output
12
题意：
众所周知出久是 OneForAll 第 9 代丐帮长老，不是非常擅长学习但是擅长惹毛爆豪。 今天出久又惹毛爆豪了，于是乎学霸爆豪反手甩了一道数学题过来。这个数学题是以序列为 背景的，给定序列求：∑i=1n∑j=in(⌊log2S(i,j)⌋+1)×(i+j)，其中 S(i,j)表示区间[i,j]的区间和。
思路：
这题暴力求取肯定是不行的，但是 log2S(i,j)的取值是不到 50 个。枚举 log2S(i,j) 的取值然后再计算，复杂度可行。
题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100010;
LL sum[maxn],p[110];
int T,n;
LL cal( LL L , LL R )
{
int l=1,r=0;
LL res = 0;
for ( int i=1 ; i<=n ; i++ )
{
if ( l<i ) l=i;
if ( r<i-1 ) r=i-1;
while( l<=n&&sum[l]-sum[i-1]<L ) l++;
while( r+1<=n&&sum[r+1]-sum[i-1]<R ) r++;
if ( l>r ) continue;
if ( sum[l]-sum[i-1]<L||sum[l]-sum[i-1]>=R ) continue;
if ( sum[r]-sum[i-1]<L||sum[r]-sum[i-1]>=R ) continue;
res += (LL)(r-l+1)*i+(LL)(l+r)*(r-l+1)/2;
}
return res;
}
int main()
{
p[0] = 1; sum[0] = 0;
for ( int i=1 ; i<=50 ; i++ )
p[i] = p[i-1]*2;
scanf ( "%d" , &T );
while ( T-- )
{
scanf ( "%d" , &n );
for ( int i=1 ; i<=n ; i++ )
{
int x; scanf ( "%d" , &x );
sum[i] = sum[i-1]+x;
}
LL res = 0;
for ( int i=1 ; i<=50 ; i++ )
res += (LL)i*cal(p[i-1],p[i]);
res += cal(0,1);
printf ( "%lld\n" , res );
}
return 0;
}
J - A hard puzzle
lcy gives a hard puzzle to feng5166,lwg,JGShining and Ignatius: gave a and b,how to know the a^b.everybody objects to this BT problem,so lcy makes the problem easier than begin.
this puzzle describes that: gave a and b,how to know the a^b's the last digit number.But everybody is too lazy to slove this problem,so they remit to you who is wise.
Input
There are mutiple test cases. Each test cases consists of two numbers a and b(0<a,b<=2^30)
Output
For each test case, you should output the a^b's last digit number.
Sample Input
7 66
8 800
Sample Output
9
6
题意：求 a^b 得最后一位
思路：快速幂或者循环节]
我参考的博客：https://blog.csdn.net/nvliba/article/details/48676659
题解:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
#define INF 0x7fffffff
const int iNF=1e8;
int POW(int a,int b){
int result=1;
int x=a%10;
while(b){
if(b&1) result=result*x%10;
x=x*x%10;
b>>=1;
}
return result;
}
int main(){
int a,b;
while(~scanf("%d%d",&a,&b)){
printf("%d\n",POW(a,b));
}
return 0;
}
K - Kingdom of Obsession
There is a kindom of obsession, so people in this kingdom do things very strictly.
They name themselves in integer, and there are nn people with their id continuous (s+1,s+2,⋯,s+n)(s+1,s+2,⋯,s+n) standing in a line in arbitrary order, be more obsessively, people with id xx wants to stand at ythyth position which satisfy
xmody=0
xmody=0
Is there any way to satisfy everyone's requirement?
Input
First line contains an integer TT, which indicates the number of test cases.
Every test case contains one line with two integers nn, ss.
Limits
1≤T≤1001≤T≤100.
1≤n≤1091≤n≤109.
0≤s≤1090≤s≤109.
Output
For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result string.
If there is any way to satisfy everyone's requirement, y equals 'Yes', otherwise y equals 'No'.
Sample Input
2
5 14
4 11
Sample Output
Case #1: No
Case #2: Yes
题意：
将 n 个数字 s+1，s+2，s+3，。。。，s+n，安排在 1，2，3，。。。，n 位置上，要求每个数 字能够整除它的位置。
思路：
小于等于 n 的数字安排在和其数字相等的位置，大于 n 的数字另外安排。另外安排 的项数超过 100 个则肯定安排不上，因为连续 100 个数字一定有两个质数。最后二分图匹配
一下，看是否能完全匹配上。
题解：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int tol,head[110];
struct edge{
int to,next;
}es[10010];
void init(){
tol = 0; memset( head , -1 , sizeof(head) );
}
void addedge( int u , int v ){
es[tol].to = v;
es[tol].next = head[u];
head[u] = tol++;
}
int linker[110],un; bool used[110];
bool dfs( int u ){
for( int i=head[u] ; i!=-1 ; i=es[i].next ){
int v = es[i].to;
if( !used[v] ){
used[v] = true;
if( linker[v]==-1||dfs( linker[v] ) ){
linker[v] = u;
return true;
}
}
}
return false;
}
int hungry(){
int res = 0;
memset( linker , -1 , sizeof(linker) );
for( int u=1 ; u<=un ; u++ ){
memset( used , false , sizeof(used) );
if( dfs(u) ) res++;
}
return res;
}
int main(){
int T;
scanf( "%d" , &T );
for( int cas=1 ; cas<=T ; cas++ ){
int n,s; scanf( "%d%d" , &n , &s );
if( min( n , s )>=100 ){
printf( "Case #%d: No\n" , cas );
}else{
init(); un = min( n , s );
for( int i=max( s+1 , n+1 ) ; i<=n+s ; i++ ){
for( int j=1 ; j<=min( n , s ) ; j++ ){
if( i%j==0 ) addedge( i-max( s , n ) , j );
}
}
if( hungry()==un ) printf( "Case #%d: Yes\n" , cas );
else printf( "Case #%d: No\n" , cas );
}
}
return 0;
}
