首先说一下这套题的反思：1细节错误反复犯，
2读题不认真，看不到操作做多只有一次，
3数组开的不够，
4做题时不知道拿纸笔推导，导致与正解擦肩而过
5盲目自信
综上所述：我就是个弟弟
A
A - Sasha and His Trip
题意：给你两个小于等于100的数， n和v， 要从1号城市花最少的钱到n号城市， 汽车最大油箱油量是v， 每移动一格都花费1的油 第i号城市单位油价是i
这道题要是粗心大意地乍一看感觉像是个比价复杂的问题，但是只要稍微一分析就知道是个贪心，在后面加油肯定不如在前面加省钱，所以我们尽可
能在前面加。但是由于油箱容量的限制，我们最开始只能加v单位的油，之后，每走一格加一次，因为只有一空我就加，在前面加肯定比留着到后面去
加要优。可是本弱这么写完之后就wa了，看着队友一个个多a了，百思不得其解到底哪里错了，我真傻，真的。我是在开始的时候给ans赋值为v，这
样的话就一定要注意如果n<=v,那么ans=n-1就可以了。当然如果换一种写法，从二到n遍历，每走一格，如果这一格的距离终点小于v，那么花费为
1（在一开始就加上了），否则花费为i，就可以避免我得这个问题了。
代码：
#include<iostream>
#include<cstdio>
using namespace std;
int n,v;
int ans;
int main()
{
cin>>n>>v;
ans=v;
for(int i=2;i+v<=n;++i)ans+=i;
if(v>n-1)ans=n-1;
printf("%d",ans);
return 0;
}
B
One day Sasha visited the farmer 2D and his famous magnetic farm. On this farm, the crop grows due to the influence of a special magnetic field. Maintaining of the magnetic field is provided by n machines, and the power of the i-th machine is ai. This year 2D decided to cultivate a new culture, but what exactly he didn't say. For the successful growth of the new
culture,it is necessary to slightly change the powers of the machines. 2D can at most once choose an arbitrary integer
x, then choose one machine and reduce the power of its machine by x times, and at the same time increase the power of
one another machine by x times (powers of all the machines must stay positive integers). Note that he may not do that if
he wants. More formally,2D can choose two such indices i and j, and one integer x such that x is a divisor of ai, and
change powers as following: ai=ai/x, aj=aj⋅x
Sasha is very curious, that's why he wants to calculate the minimum total power the farmer can reach. There are too many machines, and Sasha can't cope with computations, help him!
题目大意就是在一个序列里找一个数，他除以他的因子，让另一个乘以他的因子，然后让整个序列和变得最小，求最小的序列和。注意这样的操
作最多只能做一次，也可以不做。所以我们可以想到，如果我们让ai/x,aj*x,那么必须是ai/x>aj才会让最后的结果变小，否则ai+aj<ai/x+aj*x不如不做这
样的变幻，因为我们要求的是最小。那么，这个aj当然是选序列中最小的数最合适。我确定了这个之后，以为x选最大的ai的最大的除数就可以了，但
是这样没有道理可言，或许这个ai是素数，根本不能起到什么作用，所以我们要枚举每一个数的每一个因子，当然，因为ai<=100,n<=5e4所以我是直
接枚举每一个因子，O(100*n)的复杂度可过，如果ai的范围在大一点，我们也可只枚举到根号n，这样另一半的因子也能找出来，也可以预处理出每一
个数的因子。
代码：
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdio> 4 #include<queue> 5 using namespace std; 6 const int maxn=5e4+5; 7 int n,a[maxn]; 8 int di[110]; 9 int ans; 10 int Min=110; 11 int x; 12 int main() 13 { 14 scanf("%d",&n); 15 for(int i=1;i<=n;++i)scanf("%d",&a[i]),Min=min(Min,a[i]); 16 for(int i=1;i<=n;++i) 17 for(int j=1;j<=a[i];++j) 18 { 19 if(a[i]%j==0) 20 { 21 if((a[i]+Min-a[i]/j-Min*j)>x)x=(a[i]+Min-a[i]/j-Min*j); 22 } 23 } 24 for(int i=1;i<=n;++i)ans+=a[i]; 25 ans-=x; 26 printf("%d ",ans); 27 return 0; 28 }
C
Sasha likes programming. Once, during a very long contest, Sasha decided that he was a bit tired and needed to relax. So he did. But since Sasha isn't an ordinary guy, he prefers to relax unusually. During leisure time Sasha likes to
upsolve unsolved problems because upsolving is very useful. Therefore, Sasha decided to upsolve the following problem: You have an array a with n integers. You need to count the number of funny pairs (l,r) (l≤r). To check if a pair (l,r) is a funny pair, take mid=l+r−12, then if r−l+1 is an even number and al⊕al+1⊕…⊕amid=amid+1⊕amid+2⊕…⊕ar, then the pair is funny. In other words, ⊕ of elements of the left half of the
subarray from l to r should be equal to ⊕ of elements of the right half. Note that ⊕ denotes the bitwise XOR operation. It is time to continue solving the contest, so Sasha asked you to solve this task.
首先我们来说一下异或：按位异或是按照二进制位进行操作，当两个数的某一位都是0或者都是1的时候，结果是0，当一位是1一位是0的时候结果是
1，由此我们可以发现：一个数异或0是它本身，异或自己结果是0。由此我们可以有前缀异或和的操作，令sum[l]=a[1]^a[2]^……^a[l],sum[r]=a[1]^a[2]
……^a[r],l<r，那么sum[l-1]^sum[r]就是从a[l]到a[r]的异或和。证明：sum[l-1]^sum[l-1]=0,所以sum[l-1]^sum[r]就相当于0^(a[l]到a[r]的异或和）,就是a[l]
到a[r]的异或和。
然后我们就知道了，a[l]到a[mid]的异或和是sum[mid]^sum[l-1],a[mid+1]到a[r]的异或和是sum[r]^sum[mid]，令
sum[mid]^sum[l1]=sum[r]^sum[mid],sum[mid]可以消掉，那么就是令sum[l-1]=sum[mid]，并且由于r-(l-1)是偶数，所以区间长度是偶数的区间的个数，
怎么样，n^2的想法立马就出现了，但是数据范围是3e5，这样是不可过的。2^20=2^10*2^10，也就1e6的数量级，我们可以开一个桶，记录下每一个
前缀异或和出现的次数，当这个数再次出现的的时候，前面每一个都可以和他形成一个符合要求的区间，ans+=他曾经出现过的次数即可。还有最后一
点：我们要求区间长度是偶数，所以下标的奇偶性相同才可以构成符合要求的区间，我们开两个桶，一个记录下标是奇数的前缀异或和出现的次数，
一个记录偶数的即可。我犯的错：数组开3e5被卡边界，ans没有开long long导致wa
代码：
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int maxn=3e5+5; 5 int n; 6 int a[maxn]; 7 int b[maxn]; 8 int num[(1<<20)+10][2]; 9 long long ans; 10 int main() 11 { 12 scanf("%d",&n); 13 num[0][0]=1; 14 for(int i=1;i<=n;++i) 15 scanf("%d",&a[i]),b[i]=b[i-1]^a[i], 16 ans+=num[b[i]][(i&1)],num[b[i]][i&1]++; 17 printf("%lld ",ans); 18 return 0; 19 }
D
Reading books is one of Sasha's passions. Once while he was reading one book, he became acquainted with an unusual
character. The character told about himself like that: "Many are my names in many countries. Mithrandir among the
Elves, Tharkûn to the Dwarves, Olórin I was in my youth in the West that is forgotten, in the South Incánus, in the
North Gandalf; to the East I go not." And at that moment Sasha thought, how would that character be called in the East? In the East all names are palindromes. A string is a palindrome if it reads the same backward as forward. For example, such strings as "kazak", "oo" and "r"
are palindromes, but strings "abb" and "ij" are not. Sasha believed that the hero would be named after one of the gods of the East. As long as there couldn't be two equal
names, so in the East people did the following: they wrote the original name as a string on a piece of paper, then cut
the paper minimum number of times k, so they got k+1 pieces of paper with substrings of the initial string, and then
unite those pieces together to get a new string. Pieces couldn't be turned over, they could be shuffled. In this way, it's possible to achive a string abcdefg from the string f|de|abc|g using 3 cuts (by swapping papers with substrings f and abc). The string cbadefg can't be received using the same cuts. More formally, Sasha wants for the given palindrome s find such minimum k, that you can cut this string into k+1 parts, and then unite them in such a way that the final string will be a palindrome and it won't be equal to the initial string
s. It there is no answer, then print "Impossible" (without quotes).
很迷的一道题，我也不是很明白，首先我们知道如果一个偶数的回文串所有的数都相等，或者一个奇数的回文串，除了中间的字符其他的都相
等，那么这个怎么切都无法构成一个新的回文串，输出impossible就行咯，然后就是除去最中间那个字符，至少有两种不同的字符（当然偶数长度的串
没有最中间的字符），这样只要让某一个字符的位置改变就可以构成一个新的字符串。如果一个回文字符串他的一半也是回文的，那么我们至少切两
刀，把左右的回文串分开，分成的子串不再是回文串的样子，因为只切一刀的话，左右调换，因为是aba aba式的回文串，左右调换与原来是一样的。
对于左右子串不是回文串的样子，我们只在中间分开左右调换就会与原来的不同，因为abba事的调换过来就是baab式，当然对于奇数长度的串来说，
还是得切两刀，因为要在最中间字符的左右切。现在，我们可以确定，除了impossible，不是切一刀就是切两刀，所以我们可以遍历一下切一刀可不可
以，这样是n^2的判断，如果切一刀不行，那就是切两刀。
代码：
1 #include<iostream> 2 #include<cstring> 3 #include<string> 4 #include<cstdio> 5 using namespace std; 6 const int maxn=5e3+5; 7 char s[maxn]; 8 int len; 9 bool check() 10 { 11 int mid=1+len>>1; 12 char c=s[1]; 13 if(len&1) 14 { 15 for(int i=1;i<=len;++i) 16 { 17 if(i==mid)continue; 18 if(s[i]!=c)return 0; 19 } 20 }else 21 { 22 for(int i=1;i<=len;++i) 23 if(s[i]!=c)return 0; 24 } 25 return 1; 26 } 27 char a[maxn]; 28 int pd(int x) 29 { 30 for(int i=x+1;i<=len;++i)a[i-x]=s[i]; 31 for(int i=1;i<=x;++i)a[len-x+i]=s[i]; 32 int flag=0; 33 for(int i=1;i<=len;++i)if(a[i]!=s[i])flag=1; 34 if(!flag)return 0; 35 int mid=len>>1; 36 for(int i=1,j=len;i<=mid;i++,j--) 37 if(a[i]!=a[j])return 0; 38 return 1; 39 } 40 int main() 41 { 42 scanf("%s",s+1); 43 len=strlen(s+1); 44 if(check()) 45 { 46 printf("Impossible "); 47 return 0; 48 } 49 for(int i=1;i<=len;++i) 50 if(pd(i)) 51 { 52 printf("1 ");return 0; 53 } 54 printf("2 ");return 0; 55 }
就在刚才，在本菜鸡写d上面的解题思路的时候，有了新的想法。我们知道奇数是一定需要切两刀的，那么切一刀就是偶数串的专属，但是并不是每一
个偶数串都可以，比如mj学长的反例：abaaba,这个需要切两刀切成ab aa ba 重新组合成baaaab，其实也就是如果左右两边都是回文串的话，切一刀
是不可以的，但是我们看看最后一个样例：kinnikkinnik，这个在第三个字符后面切是可以的，我们发现，取这个回文串的一半，依然是回文串，但是
再去一半，取出来的就不是回文串了，也就是这个回文串可以看成是kni镜像，得到kniink，再镜像得到的。所以我们去找最初的这个字符串，如果这个
字符串是abc形式的，那么数据无非是abc cba abc cba这样的，把abc挪到最后，就可以得到一个新的字符串，并且是回文的，如果最后找到的是aba
形式的回文串，那么数据就应该是aba aba aba aba这样的，切出一个aba再怎么放还是与原串相同，这时候应该把开始ab和最后的ba切下来调换位
置，当然切abaa和aaba或者abaab和baaba调换都是可以的，就是不能找aba的整数倍数调换，因为那样调换前后是一样的。所以我们只需要递归的去
找最开始的这个串是abc式的还是aba式的就可以了，abc式的是可以一刀切的，而aba式的不可以。其实第一种思路遍历也是找能不能找到这样一个
abc罢了。
1 #include<iostream> 2 #include<cstring> 3 #include<string> 4 #include<cstdio> 5 using namespace std; 6 const int maxn=5e3+5; 7 char s[maxn]; 8 int len; 9 bool check() 10 { 11 int mid=1+len>>1; 12 char c=s[1]; 13 if(len&1) 14 { 15 for(int i=1;i<=len;++i) 16 { 17 if(i==mid)continue; 18 if(s[i]!=c)return 0; 19 } 20 }else 21 { 22 for(int i=1;i<=len;++i) 23 if(s[i]!=c)return 0; 24 } 25 return 1; 26 } 27 char a[maxn]; 28 bool pd(int x) 29 { 30 if(x&1)return 0; 31 if(x==0)return 0; 32 int mid=x>>1; 33 for(int i=1,j=mid;i<=mid;++i,--j) 34 if(s[i]!=s[j])return 1; 35 return pd(x>>1); 36 } 37 int main() 38 { 39 scanf("%s",s+1); 40 len=strlen(s+1); 41 if(check()) 42 { 43 printf("Impossible "); 44 return 0; 45 } 46 if(len%2==0&&(pd(len))) 47 printf("1 "); 48 else printf("2 "); 49 }