2021CCPC竞赛网络选拔赛（第一场）部分题解
前言
随着8月28号下午5点一到，今年ccpc选拔赛落下帷幕，自闭的五小时也就这样结束了
首先，打完这场比赛我深刻认识到自己的菜鸡程度，突然感觉回家种田也许是个不错的选择…
其次，这次的比赛可以说是我打的最艰辛的一场了，杭电oj炸了5小时，为了看有没有过代码就在那蒽刷榜单，给人整麻了，然后举办方成功的发现这比赛得重开了…自闭完5小时没想到还有第二次…
1001 Cut The Wire
Problem Description：
In the country of Infinity , there is a strange road. This road only has a starting point, but no end. Since this road is infinite, there are also countless street lights. The street lights are numbered from 1(the starting point) to infinity. The street lights are connected by wires under a strange law:
For a street light x,
if x is even, then x is connected with x2 by a wire;
if x is odd, then x and 3x+1 is connected by a wire.
Now Kris is standing in the middle of street light n and n+1, and he is able to cut all wires passing by. That is, he will cut all wires connecting street lights a and b satisfying a≤n and b>n.
Now he wonders, how many wires he will cut. Please help him calculate.
Input：
This problem contains multiple test cases.
The first line contains an integer T(1≤T≤105) indicating the number of test cases.
The next T lines each contains one integer n(1≤n≤109).
Output：
For each test case, output one line of one integer indicating the answer.
Sample Input：
2
12
60
Sample Output：
10
50
题意：
有一个无限长的x正整数轴，轴上每个点都代表一个路灯，路灯由电线连着。
对于第x盏路灯，如果x是奇数，那么他（x）和第 3x+1 盏路灯相连；如果x是偶数，那么他（x）和第 x / 2 盏路灯相连。
你现在站在第n和n+1的路灯之间，经过你的电线你可以一刀切断，也就是说当两盏能够相连的路灯a，b满足a<=n且b>n就算做一条经过你的电线，求你能斩断多少条电线
思路：
其实理解了题意就会了，以n为界限，如果i<n，那么i就不可能是偶数（i和i/2必定小于n，电线过不来），如果i>n，那么i就不能是奇数（i和3i+1必大于n，电线也过不来）
那么，这题就是求当i<n时，i为奇数的最小值到n之间的奇数个数；当i>n时，i为偶数到i*2之间的偶数个数。两者相加就是答案
代码：
#include <iostream>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
const int INF=100000000;
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
int ans=0;
cin>>n;
if(n%2==0)//分情况讨论，如果n是偶数的话
{
ans+= (n/2);//n右边只能是偶数才能切，偶数个数是（终点-n）/2由于终点=n*2，所以简化算式就是n/2
int temp=0;
temp=(n/3);//n左边只能是奇数，而奇数必须有个起点，当n是偶数时起点就是先n/3就行
if(temp%2==0) temp=temp+1;//如果起点是偶数就向上取一个奇数
else temp=temp+2;//如果起点算出是奇数，由于3x+1>=n+1向上取整，所以+2
ans+=((n+1)-temp)/2;
}
else//如果n是奇数
{
ans+=(n+1)/2;//当n是奇数，右边偶数的个数
int temp=0;
temp=ceil((double)n*1.0/3);//n是奇数，求起点，向上取整后
if(temp%2==0) temp=temp+1;//如果起点是偶数+1变成奇数，如果是奇数那就是起点
ans+=((n+1)-temp)/2;
ans+=1;//加上n与3n+1这一条线
}
cout<<ans<<endl;
}
return 0;
}
1006 Power Sum
Problem Description:
Given a positive number n, Kris needs to find a positive number k and an array {ai}(ai∈{?1,1}) of length k(1≤k≤n+2), such that:
This is too hard for Kris so you have to help him.
Input:
The input contains multiple test cases.
The first line contains an integer T(1≤T≤100) indicating the number of test cases.
Each of the next T lines contains one integer n(1≤n≤106).
It’s guaranteed that ∑n≤3?107.
Output:
The output should contain 2T lines. For each test case, output two lines.
The first line contains one integer, k.
The second line contains a 01-string of length k representing the array, with 0 in the ith position denoting ai=?1 and 1 denoting ai=1.
If there are multiple answers, print any.
Sample Input
2
1
5
Sample Output
1
1
2
11
题意：
给你一个n，对 i2 (i=1、2、3、4…)进行*-1或者*1的操作然后把他们相加，结果等于n就行，问你需要多少个 i2 才能让他们相加等于n（需要的个数不能超过n+2个），输出你需要的个数k以及你是如何对他们进行赋值操作的，对i2 取负数输出0，取整数输出1
思路：
由 :
n2- (n+1)2 = -2*n-1
可以推导出:
+n2- (n+1)2 - (n+2)2 + (n+3)2 = -2n-1 - (-2(n+2)-1) = -2n-1+2n+4+1 = 4
(也可以自己试着找规律)
可以得出1 4 9 16 25 36…这组数任意四个数按照"1001"方式赋值（也就是"+、-、-、+“的方式赋值）加起来一定等于4，那么这道题就转换成了给你一个n，你先求出n/4的值（ 也就是求出需要多少组"1001" ），然后再求出n%4的值（ 也就是求出我取完所有"1001"距离实际值还差多少 ）
易得：1=“1”； 2=“0001”； 3=“01”;
令k = n/4;
n%4 = 0时，我只需要k组"1001”，长度为k x 4；
n%4 = 1时；我除了需要k组"1001"还要一个"1"才能相加为n，字符长度为k x 4 + 1;
n%4 = 2时；我除了需要k组"1001"还要一个"0001"才能相加为n，字符长度为k x 4 + 4;
n%4 = 3时；我除了需要k组"1001"还要一个"01"才能相加为n，字符长度为k x 4 + 2;
代码：
#include<iostream>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--){
int n, remain = 0, group = 0;
cin>>n;
remain = n % 4;//还需要多少等于n
group = n / 4;//需要多少（k）组"1001"
if(remain==0){
for(int i=0;i<group;i++){
cout<<group*4<<endl;//长度k*4
cout<<"1001";
}
cout<<endl;
}
if(remain==1){
cout<<group*4+1<<endl;
cout<<"1";
for(int i=0;i<group;i++){
cout<<"1001";
}//长度k*4+1
cout<<endl;
}
if(remain==2){
cout<<group*4+4<<endl;
cout<<"0001";
for(int i=0;i<group;i++){
cout<<"1001";
}//长度k*4+4
cout<<endl;
}
if(remain==3){
cout<<group*4+2<<endl;
cout<<"01";
for(int i=0;i<group;i++){
cout<<"1001";
}//长度k*4+2
cout<<endl;
}
}
return 0;
}
1009 Command Sequence
Problem Description:
There is a robot that can move by receiving a sequence of commands.
There are four types of command in the command sequence:
U: robot moves one unit up.
D: robot moves one unit down.
L: robot moves one unit left.
R: robot moves one unit right.
Now, given a command sequence of length n. You need to find out how many substrings of the command sequence satisfy that if the robot execute the substring command, it can return to the starting position.
A substring is a contiguous sequence of characters within a string. For instance, “the best of” is a substring of “It was the best of times”. For example, “Itwastimes” is a subsequence of “It was the best of times”, but not a substring.
Input:
This problem contains multiple test cases.
The first line contains an integer t (1≤t≤20) indicating the number of test cases.
For each test case, the first line contains one integer n (2≤n≤105).
The second line contains a UDLR string of length n.
Output
For each test case, output one line one integer indicating the answer.
Sample Input
1
6
URLLDR
Sample Output
2
题意：
给一个机器人一串代码指令：
U：向上走
D：向下走
R：向右走
L：向左走
求其中有多少子字符串（连续的）指令单独给机器人可以让它从起点开始出发最后回到起点（可以重复回到起点只要最后停在起点就行）
思路：
设置向右走是+1，左是-1，上是+3x105，下是-30x105，执行一次命令就把结果存起来，最后数相同的数字可以组合多少，把每组相同数的组合数加起来就是答案
如果两个数相同，我们可以把它们看成是起点0，不管它们中间怎么走，最后都回到了0起点
如果用纯数组去做然后求n*（n+1）/2会很麻烦，可能会发生例如：3005这个数最后经过3次，但顺序处理数组可能会把他为2时的数据一起存入，导致结果偏大
所以我们选择用map去代替计算n*（n+1）/2
代码：
#include<iostream>
#include<map>
using namespace std;
map<long long,long long>pos;
const int maxn = 1e6;
char rob[maxn];
int main()
{
int t;
cin>>t;
while(t--){
int n, value = 0;//value把字符转换为数字形式
long long ans = 0, sum = 0;
cin>>n;
for(int i=0;i<n;i++){
cin>>rob[i];
}
pos.clear();
pos[0] = 1;
for(int i=0;i<n;i++){
if(rob[i]=='U') value = 3e5;
if(rob[i]=='D') value = -3e5;
if(rob[i]=='R') value = 1;
if(rob[i]=='L') value = -1;
sum += value;//累加
ans += pos[sum];//如果这个数第一次出现就开辟出来，初始值为0
pos[sum] += 1;//这个点经过一次
}
cout<<ans<<endl;
}
return 0;
}
总结
经历了这场比赛我深刻认识到自己的弱鸡程度，当了两年acmer跟白学了一样…希望重赛不要跟这次一样不忍直视了
还有:请求HDU早日升级服务器!
