A
The king is left alone on the chessboard. In spite of this loneliness, he doesn’t lose heart, because he has business of national importance. For example, he has to pay an official visit to square t. As the king is not in habit of wasting his time, he wants to get from his current position s to square t in the least number of moves. Help him to do this.
In one move the king can get to the square that has a common side or a common vertex with the square the king is currently in (generally there are 8 different squares he can move to).
Input
The first line contains the chessboard coordinates of square s, the second line — of square t.
Chessboard coordinates consist of two characters, the first one is a lowercase Latin letter (from a to h), the second one is a digit from 1 to 8.
Output
In the first line print n — minimum number of the king’s moves. Then in n lines print the moves themselves. Each move is described with one of the 8: L, R, U, D, LU, LD, RU or RD.
L, R, U, D stand respectively for moves left, right, up and down (according to the picture), and 2-letter combinations stand for diagonal moves. If the answer is not unique, print any of them.
Example
Input
a8
h1
Output
7
RD
RD
RD
RD
RD
RD
RD
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int tl[]= {0,0,1,-1,1,1,-1,-1};
int tr[]= {1,-1,0,0,1,-1,1,-1};
string y[9]= {"U","D","R","L","RU","RD","LU","LD"};
struct node
{
int x,y,d;
vector<int>lu;
};
int main()
{
char a[10],b[10];
cin>>a>>b;
int s1,s2,e1,e2;
s1 = a[0]-'a'+1;
s2 = b[0]-'a'+1;
e1 = a[1]-'0';
e2 = b[1]-'0';
//cout<<s1<<" "<<s2<<" "<<e1<<" "<<e2<<endl;
int mmax = max(abs(s2-s1),abs(e2-e1));
int mmin = min(abs(s2-s1),abs(e2-e1));
cout<<mmax<<endl;
mmax= mmax-mmin;
while(mmin--)
{
if(s1<s2&&e1<e2)
{
printf("RU\n");
s1++;
e1++;
}
if(s1<s2&&e1>e2)
{
printf("RD\n");
s1++;
e2++;
}
if(s1>s2&&e1<e2)
{
printf("LU\n");
s2++;
e1++;
}
if(s1>s2&&e1>e2)
{
printf("LD\n");
s2++;
e2++;
}
}
while(mmax--)
{
if(e1>e2)printf("D\n");
if(e1<e2)printf("U\n");
if(s1>s2)printf("L\n");
if(s1<s2)printf("R\n");
}
return 0;
}
C： 指针或尺取+优先队列：
KSUM: Maximum K Sums
题目描述
大厨非常喜欢数组。这天，他得到了一个长度为 N 的正整数数组 A。
大厨求出了 A 的所有子段的和，并将这 N(N + 1)/2 个数字排成了降序，记为序列 L。大厨
想要知道 L 的前 K 个元素是什么，请帮帮他。
输入格式
输入数据的第一行包含两个整数 N 和 K。接下来一行包含 N 个整数，代表数组 A。
输出格式
输出 K 个数，代表序列 L 的前 K 个元素，用空格隔开。
数据范围和子任务
• 1 ≤ N ≤ 105
• 1 ≤ K ≤ min(N(N + 1)/2, 105
)
• 1 ≤ Ai ≤ 109
子任务 1（47 分）：
• 1 ≤ N ≤ 1000
子任务 2（53 分）：
• 1 ≤ N ≤ 105
样例数据
输入
3 4
1 3 4
输出
8 7 4 4
输入
3 3
10 2 7
输出
19 12 10
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = (int )1e5+5;
set<pair<ll,int>,greater<pair<ll,int> > >s;
int n,k,f[N];
ll p[N];
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
p[i] = p[i-1]+a;
s.insert(make_pair(p[i],i));
}
while(k--)
{
printf("%lld ",s.begin()->first);
int i = s.begin()->second;
s.erase(s.begin());
if(++f[i]<i)
{
s.insert(make_pair(p[i]-p[f[i]],i));
}
// cout<<i<<" "<<f[i]<<" "<<p[i]-p[f[i]]<<endl;
// for(int i=1;i<=5;i++)
// cout<<f[i]<<" ";
// cout<<endl<<endl;
}
return 0;
}
F HackerRank string-reduction
String Reduction
Given a string consisting of a,b and c’s, we can perform the following operation: Take any two adjacent distinct characters and replace it with the third character. For example, if ‘a’ and ‘c’ are adjacent, they can replaced with ‘b’. What is the smallest string which can result by applying this operation repeatedly?
For example, you can either get cab -> cc or cab -> bb, resulting in a string of length 2.
For the second case, one optimal solution is: bcab -> aab -> ac -> b. No more operations can be applied and the resultant string has length 1.
字符串中任意两个相邻的不同字符都可以替换为第三种字符,问你一个字符串被多次替换后可以剩下的最短长度为多少.
解答:
这个问题的答案让人拍手称快. 分为三种情况:
首先,如果字符串中字符全部一样,那么直接返回该字符串的长度即可.
其次,如果三种字符的个数都是奇数或者都是偶数,那么答案为2
其他情况,返回1.
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
string a;
int n;
cin>>n;
while(n--)
{
cin>>a;
int book[20]={0};
for(int i=0;a[i];i++)
{
book[a[i]-'a']++;
}
int u = 0;
for(int i=0;i<=2;i++)
if(book[i]==0)
u++;
if(u==2)cout<<a.size()<<endl;
else if(book[0]%2==0&&book[1]%2==0&&book[2]%2==0)
{
printf("2\n");
}
else if(book[0]%2==1&&book[1]%2==1&&book[2]%2==1)
{
printf("2\n");
}
else printf("1\n");
}
return 0;
}
尺取
G - Books CodeForces - 279B
When Valera has got some free time, he goes to the library to read some books. Today he’s got t free minutes to read. That’s why Valera took n books in the library and for each book he estimated the time he is going to need to read it. Let’s number the books by integers from 1 to n. Valera needs ai minutes to read the i-th book.
Valera decided to choose an arbitrary book with number i and read the books one by one, starting from this book. In other words, he will first read book number i, then book number i + 1, then book number i + 2 and so on. He continues the process until he either runs out of the free time or finishes reading the n-th book. Valera reads each book up to the end, that is, he doesn’t start reading the book if he doesn’t have enough free time to finish reading it.
Print the maximum number of books Valera can read.
Input
The first line contains two integers n and t (1 ≤ n ≤ 105; 1 ≤ t ≤ 109) — the number of books and the number of free minutes Valera’s got. The second line contains a sequence of n integers a1, a2, …, an (1 ≤ ai ≤ 104), where number ai shows the number of minutes that the boy needs to read the i-th book.
Output
Print a single integer — the maximum number of books Valera can read.
Example
Input
4 5
3 1 2 1
Output
3
Input
3 3
2 2 3
Output
1
列出看每本书所需要的时间，给你 t 时间，问怎样才能看最多本书。要注意的是，看完最后一本之后不能回头看前面的。
用dp的方法一段段求。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int mx = 1e5 + 5;
int lt[mx], dp[mx], sum, n ,t;
int main(){
scanf("%d%d", &n, &t);
for(int i =1; i <= n; i++)
scanf("%d", <[i]);
dp[0] = 1;
lt[0] = sum = 0;
int j = 1;
for(int i = 1; i <= n; i++){
dp[i] = dp[i-1] - 1;
sum = sum - lt[i-1];
//cout<<"sum="<<sum<<endl;
for( ; j <= n; j++){
if(sum + lt[j] <= t){
sum += lt[j];
//cout<<"sum="<<sum<<endl;
dp[i]++;
}
else break;
}
// cout<<"i=="<<i<<"dp=="<<dp[i]<<endl;
// cout<<"sum=="<<sum<<endl;
}
int re = dp[1];
for(int i = 2; i <= n; i++)
re =max(re, dp[i]);
printf("%d\n", re);
// for(int i = 1; i <= n; i++)
// cout<<dp[i]<<endl;
return 0;
}统计加二分查找。。
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <stack>
using namespace std;
int main()
{
int n, t, a[100005], ans;
while(~scanf("%d %d", &n, &t))
{
a[0] = 0;
ans = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
a[i] += a[i-1];
}
for(int i = 0; i < n; i++)
{
int left = i+1;
int right = n;
while(left <= right)
{
int mid = (left + right) / 2;
if(a[mid] - a[i] <= t)
{
left = mid + 1;
}
else
{
right = mid - 1;
}
}
ans = max(left - i, ans);
}
printf("%d\n", ans-1);
}
return 0;
}尺取
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int a[199999]={0};
int main()
{
int n,sum;
cin>>n>>sum;
int x;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
a[i] = a[i-1]+x;
}
int y = 0 ;
int right = 0;
for(int i=1;i<=n;i++)
{
while(right<n&&a[right+1]-a[i-1]<=sum)
right++;
y = max(y,right-i+1);
}
cout<<y<<endl;
return 0;
}
京公网安备 11010502036488号