GroupBlog

A.解方程

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

给出n个整数和x，请问这n个整数中是否存在三个数a，b，c使得ax 2+bx+c=0，数字可以重复使用。

输入描述:

第一行两个整数n，x
第二行n个整数a[i]表示可以用的数
1 <= n <= 1000, -1000 <= a[i], x <= 1000

输出描述:

YES表示可以
NO表示不可以

示例1

输入

2 1
1 -2

输出

YES

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
  
typedef long long ll;
  
 
int main() {
    ll a[1005];
      
    set<ll> s;
    int n;
    int x;
      
    scanf("%d %d",&n,&x);
      
    for(int i = 0;i < n;i++) {
        scanf("%lld",&a[i]);
        s.insert(a[i]);
    }
      
  
    bool flag = false;
    for(int i = 0;i < n;i++) {
        if(flag) {
            break;
        }
        for(int j = 0;j < n;j++) {
            if(flag) {
                break;
            }
            ll tmp = -(a[i] * x * x + a[j] * x);
            if(s.count(tmp)) {
                flag = true;
                break;
            }
        }
    }
     
    if(flag) {
        printf("YES\n");
    } else {
        printf("NO\n");
    }
      
    return 0;
}

c.割草机

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

有一块n*m的地，每块地要么长满杂草(用' W'表示)，要么是空地(用' G'表示)，现在有一个人站在(1,1)，面向(1,m),他可以按如下两种方式移动：

1、向面朝的方向移动一格，耗费1单位时间

2、向下移动一格，并反转面朝的方向(右变左，左变右)，耗费1单位时间

现在他想知道清除所有的杂草最少需要多少单位时间(清除完杂草之后不用返回(1,1))

输入描述:

第一行n,m
接下来n行每行一个字符串表示矩阵。
n,m<=150

输出描述:

一行一个整数表示答案。

示例1

输入

4 5
GWGGW
GGWGG
GWGGG
WGGGG

输出

示例2

输入

3 3
GWW
WWW
WWG

输出

#include <iostream>
#include <cstdio>

using namespace std;

char mp[155][155];
int l[155];
int r[155];

int main() {
    int m;
    int n;
    
    cin >> n >> m;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            cin >> mp[i][j];
        }
    }
    int last = 0;
    for (int i = 1;i <= n;++i){
        l[i] = m+1,r[i] = 0;
        for (int j = 1;j <= m;++j) 
            if (mp[i][j]=='W') {
                l[i] = min(l[i],j);
                r[i] = max(r[i],j);
                last = i;
            }
    }
    l[n+1] = m+1; r[n+1] = 0;
    int ans = -1;
    int now = 1;
    for (int i = 1;i <= last;++i){
        ++ans;
        if (i&1){
            int aim = max(r[i],r[i+1]); 
            aim = max(aim,now);
            ans += aim-now; 
            now = aim;
        } else {
            int aim = min(l[i],l[i+1]); 
            aim = min(aim,now);
            ans += now-aim; 
            now = aim;
        }
    }
    printf("%d\n",ans);
    
    return 0;
}