Where do odds begin, and where do they end? Where does hope emerge, and will they ever break?
Given an integer sequence a1, a2, ..., an of length n. Decide whether it is possible to divide it into an odd number of non-empty subsegments, the each of which has an odd length and begins and ends with odd numbers.
A subsegment is a contiguous slice of the whole sequence. For example, {3, 4, 5} and {1} are subsegments of sequence{1, 2, 3, 4, 5, 6}, while {1, 2, 4} and {7} are not.
The first line of input contains a non-negative integer n (1 ≤ n ≤ 100) — the length of the sequence.
The second line contains n space-separated non-negative integers a1, a2, ..., an (0 ≤ ai ≤ 100) — the elements of the sequence.
Output "Yes" if it's possible to fulfill the requirements, and "No" otherwise.
You can output each letter in any case (upper or lower).
3 1 3 5
Yes
5 1 0 1 5 1
Yes
3 4 3 1
No
4 3 9 9 3
No
In the first example, divide the sequence into 1 subsegment: {1, 3, 5} and the requirements will be met.
In the second example, divide the sequence into 3 subsegments: {1, 0, 1}, {5}, {1}.
In the third example, one of the subsegments must start with 4 which is an even number, thus the requirements cannot be met.
In the fourth example, the sequence can be divided into 2 subsegments: {3, 9, 9}, {3}, but this is not a valid solution because 2 is an even number.
两个奇数长度子串能够合成一个偶数长度串，一个奇数长度串+偶数长度串是依然是奇数长度串。
因此也就是可以凭空减少两个奇数子串，因此最后的答案就是奇数子串的奇偶性。
#include<bits/stdc++.h>
using namespace std;
int a[105];
int main(){
int n;
while(cin>>n){
for(int i=1;i<=n;i++)
cin>>a[i];
if(a[1]%2==0||a[n]%2==0){
cout<<"No"<<endl;
continue;
}
int cnt=0;
int temp=1;
for(int i=1;i<=n;i++){
int cc =0 ;
if(a[i]%2==1){
cc = i-temp;
temp=i;
}
if(cc%2==1)cnt++;
}
if(cnt%2==0)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return 0;
}Connect the countless points with lines, till we reach the faraway yonder.
There are n points on a coordinate plane, the i-th of which being (i, yi).
Determine whether it's possible to draw two parallel and non-overlapping lines, such that every point in the set lies on exactly one of them, and each of them passes through at least one point in the set.
The first line of input contains a positive integer n (3 ≤ n ≤ 1 000) — the number of points.
The second line contains n space-separated integers y1, y2, ..., yn ( - 109 ≤ yi ≤ 109) — the vertical coordinates of each point.
Output "Yes" (without quotes) if it's possible to fulfill the requirements, and "No" otherwise.
You can print each letter in any case (upper or lower).
5 7 5 8 6 9
Yes
5 -1 -2 0 0 -5
No
5 5 4 3 2 1
No
5 1000000000 0 0 0 0
Yes
In the first example, there are five points: (1, 7), (2, 5), (3, 8), (4, 6) and (5, 9). It's possible to draw a line that passes through points1, 3, 5, and another one that passes through points 2, 4 and is parallel to the first one.
In the second example, while it's possible to draw two lines that cover all points, they cannot be made parallel.
In the third example, it's impossible to satisfy both requirements at the same time.
题意：给定n个点，下标代表x值，值代表y值，现在要判断是否存在两条平行且不重合的直线可以穿过所有的点。
只用枚举（1,3）（1,2）（2,3）这三种情况，分别算出各情况的斜率和截距，然后带入其他点验证即可。如果不在当前直线的点，再次计算斜率，判断是否完全覆盖和平行就好了。也就是说，我们先去分别枚举第一个点与第二个点、第三个点之间的斜率k1,k2，如果与真正的斜率不同，则第一个点与第二个点不在同一直线上，与第三个点也不在同一直线上，那么说明第二个点和第三个点一定在同一直线上，算出斜率k3,真正的斜率一定是这三个里的一个。然后再去对每个斜率检查一下是否满足题目要求即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1005;
int n;
int y[maxn];
bool solve(double k)
{
int flag=0;
int point=-1; //第一个点和第point个点是两个基准点
for(int i=2;i<=n;i++)
{
if(y[i]-y[1]==k*(i-1)) continue;
flag=1; //有两条不同的直线
if(point<0) point=i;
else if(y[i]-y[point]!=k*(i-point)) //超过了两条直线
{
flag=0;
break;
}
}
if(flag) return true;
return false;
}
int main()
{
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
{
scanf("%d",&y[i]);
}
double k1=1.0*(y[2]-y[1]);
double k2=0.5*(y[3]-y[1]);
double k3=1.0*(y[3]-y[2]);
if(solve(k1)||solve(k2)||solve(k3)) puts("Yes");
else puts("No");
}
return 0;
} From beginning till end, this message has been waiting to be conveyed.
For a given unordered multiset of n lowercase English letters ("multi" means that a letter may appear more than once), we treat all letters as strings of length 1, and repeat the following operation n - 1 times:
- Remove any two elements s and t from the set, and add their concatenation s + t to the set.
The cost of such operation is defined to be 
Given a non-negative integer k, construct any valid non-empty set of no more than 100 000 letters, such that the minimum accumulative cost of the whole process is exactly k. It can be shown that a solution always exists.
The first and only line of input contains a non-negative integer k (0 ≤ k ≤ 100 000) — the required minimum cost.
Output a non-empty string of no more than 100 000 lowercase English letters — any multiset satisfying the requirements, concatenated to be a string.
Note that the printed string doesn't need to be the final concatenated string. It only needs to represent an unordered multiset of letters.
12
abababab
3
codeforces
For the multiset {'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b'}, one of the ways to complete the process is as follows:
- {"ab", "a", "b", "a", "b", "a", "b"}, with a cost of 0;
- {"aba", "b", "a", "b", "a", "b"}, with a cost of 1;
- {"abab", "a", "b", "a", "b"}, with a cost of 1;
- {"abab", "ab", "a", "b"}, with a cost of 0;
- {"abab", "aba", "b"}, with a cost of 1;
- {"abab", "abab"}, with a cost of 1;
- {"abababab"}, with a cost of 8.
The total cost is 12, and it can be proved to be the minimum cost of the process.
就是在一个集合中任取两个元素(每个元素也是一个集合)，对于两个元素共同拥有的元素在取出的那两个元素中分别出现的次数的乘积就是花费
然后再将两个元素删掉，合并成一个元素再放进去
重复上述步骤，直到集合只有一个元素
f(s,a)∗f(t,a)+f(s,b)∗f(t,b)+f(s,c)∗f(t,c)+f(s,d)∗f(t,d)+......+f(s,z)∗f(t,z) 就这样
至于代码，在纸上画画就能看出来
比如aaaa,可以分为{a,a,a,a}−>{aa,a,a}−>{aaa,a}−>{aaaa},花费分别是0，1，2，3，总花费为6，这一个字母凑不够，就用下个字母继续凑，还要特判0
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int k,sum = 0;
cin >> k;
if(k == 0)
{
cout << "a" <<endl;
return 0;
}
string res = "";
for(char i = 'a'; i <= 'z'; ++i)
{
if(sum == k) break;
for(int j = 0; j+sum <= k; ++j)
{
sum += j;
res += i;
}
}
cout << res << endl;
return 0;
}
京公网安备 11010502036488号