C/C++教程

河南十三届ICPC部分题解

本文主要是介绍河南十三届ICPC部分题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

A.祝融传火

输入之后,暴力枚举\((x,y)\)判断即可

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int n , m , a[N][N] , h , w ;
bool flag = 0;

inline int read()
{
      int x = 0;
      char ch = getchar();
    while( ch < '0' || ch > '9' ) ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
    return x;
}

int main()
{
    n = read() , m = read();
    for( int i = 1 ; i <= n ; i ++ )
    {
        for( int j = 1 ; j <= m ; j ++ ) a[i][j] = read();
    }
    h = read() - 1, w = read() - 1;
    for( int i = 1 ; i + h <= n && flag == 0 ; i ++ )
    {
        for( int j = 1 ; j + w <= m && flag == 0; j ++ )
        {
            if( a[i][j] == a[ i + h ][j] && a[i][j] == a[i][ j + w ] && a[i][j] == a[ i + h ][ j + w ] ) flag = 1;
        }
    }
    if( flag ) puts("YES");
    else puts("NO");
    return 0;
}

E. Dance with a stick

找规律题

如果有偶数个点一定不可以

如果是奇数个点最中间的点一定可以,这里的最中间是只按照横坐标排序最中间的一个,纵坐标也可以

方向指向无穷就行

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+5;

struct Node {
	int x, y;
}a[N];

int MM = 1e9;
bool cmp(Node s, Node t) {
	return s.x < t.x;
}

int main(void) {
	int n; cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
	if(n % 2 == 0) {
		puts("No");
		return 0;
	}
    sort(a + 1, a + 1 + n, cmp);
	puts("Yes");
	printf("%d %d 1 %d\n", a[n / 2 + 1].x, a[n / 2 + 1].y, -MM);
	return 0;
}

F. 图像识别

大水题,找到原点即可

#include <bits/stdc++.h>

using namespace std;

char mp[1100][1100];

int main(void) {
	int n, m;
	cin >> n >> m;
	int x = 0, y = 0;
	int dx, dy;
	for(int i = 1; i <= n; i++) {
		int flag = 1;
		for(int j = 1; j <= m; j++) {
			cin >> mp[i][j];
			if(mp[i][j] != '*') flag = 0;
			if(mp[i][j] == '#') {
				dx = j, dy = i;
			}
		}
		if(flag) y = i;
	}
	for(int j = 1; j <= m; j++) {
		int flag = 1;
		for(int i = 1; i <= n; i++) {
			if(mp[i][j] != '*') {
				flag = 0;
				break;
			}
		}
		if(flag) x = j;
	}
	printf("%d %d\n", dx - x, y - dy);
    
	return 0;
}

I.七便士

把这个六芒星展开成环,顺序是1 4 7 2 5 8 3 6

然后随便找一个黑色点破环成立链,扫描连续的白色点,假如白色点长度为x则最多可染色点数为x-1

判断即可

#include <bits/stdc++.h>
using namespace std;

const int mp[] = { 0 , 1 , 4 , 7 , 2 , 5 , 8 , 3 , 6 };
int t , cnt , sta;
bool a[20];
string s;


void solove()
{
    cin >> s;
    memset( a , 0 , sizeof( a ) ) , cnt = 0;
    for( int i = 1 , p ; i <= 8 ; i ++ )
    {
        p = s[ i - 1 ] - '0';
        if( p ) a[ mp[i] ] = a[ mp[i] + 8 ] = 1 , cnt ++;
    }
    if( cnt <= 1 )
    {
        puts("Yes");
        return ;
    }
    for( sta = 1 ; sta <= 8 && !a[ sta ]; sta ++ );
    for( int i = sta , j ; i <= sta + 7 ; i ++ )
    {
        if( a[i] ) continue;
        for( j = i + 1 ; j <= sta + 7 && !a[j] ; j ++ );
        cnt += ( j - i - 1);
        i = j;
    }
    if( cnt == 7 ) puts("Yes");
    else puts("No");
    return ;
}

int main()
{
    cin >> t;
    while( t -- ) solove();
    return 0;
}

J.甜甜圈

首先我们将两个数列的顶放在中间进行,比如样例就是5 4 1 2 7 3

然后我们维护一个top就是两个数列的顶,每次最大值和top之间的甜甜圈数量就是操作的权值

然后我们吃掉甜甜圈,并将top移动到甜甜圈处,甜甜圈我们可以用树状数组来维护是否被吃掉

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5+5;

#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1

int ans = 0;
int c[N];
int n, m;

struct Node {
	int x, y;
}arr[N];

int a[N];

bool cmp(Node s, Node t) {
	return s.x > t.x;
}

int lowbit(int x){
	return x&(-x);
}
void updata(int i,int k){    //在i位置加上k
	while(i <= n + m){
		c[i] += k;
		i += lowbit(i);
	}
}
int getsum(int i){        //求A[1 - i]的和
	int res = 0;
	while(i > 0){
		res += c[i];
		i -= lowbit(i);
	}
	return res;
}

signed main(void) {
	std::ios::sync_with_stdio(false);
	cin >> n >> m;
    int tp = n;
	for(int i = n; i >= 1; i--) {
		cin >> a[i];
	}
	for(int i = n + 1; i <= n + m; i++) {
		cin >> a[i];
	}
	for(int i = 1; i <= n + m; i++) {
		arr[i].x = a[i];
		arr[i].y = i;
	}
	sort(arr + 1, arr + 1 + n + m, cmp);
	for(int i = 1; i <= n + m; i++) {
		updata(i, 1);
	}
    arr[0].y = n;
	for( int i = 1 ; i <= n + m ; i ++)
	{
        updata( arr[i].y , -1 );
        ans += abs( getsum(arr[i - 1].y) - getsum( arr[i].y ) );
	}
	cout<< ans << endl;
	return 0;
}

L.手动计算

据说可以用积分求出面积,但是本题的精度要求并不高,所以我们可以将该图形放在网格中数网格数来求面积,因为要控制精度,所以单位面积是0.0001就可以

#include <bits/stdc++.h>

using namespace std;

void solve() {
	double a, b, c, d;
	cin >> a >> b >> c >> d;
	double ans = 0;
	for(double i = -8; i <= 8; i += 0.01) {
		for(double j = -8; j <= 8; j += 0.01) {
			if((i * i * b * b + j * j * a * a) < a * a * b * b || (i * i * d * d + j * j * c * c) < c * c * d * d) {
				ans += 0.01 * 0.01;
			}
		}
	}
	printf("%.1lf\n", ans);
}

int main(void) {
	int T; cin >> T;
	while(T--) {
		solve();
	}
	return 0;
}

M.输入输出

乍一看很难,但是细读题目就会发现题目要求\([l_i,R_i]\)之间必须全部为黑色,其他全部为白色实际已经告诉了我们答案只需求\(\sum (R_i-L_i)\)即可\(a_i\)实际上没用,反过来细品为啥题目叫输入输出

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n , m , k , a[N] , l_min = N , r_max = -1 , ans , ls , rs , color[N];


inline int read()
{
      int x = 0;
      char ch = getchar();
    while( ch < '0' || ch > '9' ) ch = getchar();
    while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - '0' , ch = getchar();
    return x;
}

int main()
{
    n = read() , m = read() , k = read();
    for(   int i = 1 , l , r ; i <= m ; i ++ )
    {
        l = read() , r = read();
        ans += r - l ;
    }
    cout << ans << endl;
}
这篇关于河南十三届ICPC部分题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!