CodeforcesRound#296(Div.2)A,B,C,D

作者：俺是胖墩墩_499 | 来源：互联网 | 2023-10-12 17:39

A-PlayingwithPaper:问一个矩阵最多能被切成多少个正方形。暴力即可#include<map>#include<set>#inc

A - Playing with Paper: 问一个矩阵最多能被切成多少个正方形。暴力即可

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define lson l, mid, rt <<1
#define rson mid + 1, r, rt <<1 | 1
#define pi acos(-1.0)
#define eps 1e-8
typedef long long ll;
const int inf = 0x3f3f3f3f;

ll n, m;

int main()
{
    while( cin >> n >> m )
    {
        ll ans = 0;
        while( 1 )
        {
            if( n % m == 0 )
            {
                ans += n / m;
                break;
            }
            ans += n / m;
            n = n - n / m * m;
            swap( n, m );
        }
        cout < 
 
 
 B - Error Correct System ：问两个长度相同的串通过交换随意的两个字符能不能使同样位置的不同字符的数尽可能少，输出交换后相同位置的不同的数，如果可以减少的话，输出使减少数量最大的两个位置 
 对不同的位置的两个字母建边，然后三重循环找答案 
  
 #include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define lson l, mid, rt <<1
#define rson mid + 1, r, rt <<1 | 1
#define pi acos(-1.0)
#define eps 1e-8
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 200010;

char a[N], c[N];
int n;

int mat[30][30];

int main()
{
    while(~scanf("%d", &n))
    {
        int cnt = 0;
        int p1, p2;
        memset( mat, -1, sizeof( mat ) );
        scanf("%s %s", a, c);
        for( int i = 0; i  0 )
                {
                    if( mat[j][i] > 0 )
                    {
                        printf("%d\n%d %d\n", cnt-2, mat[i][j], mat[j][i]);
                        OK = 1;
                        break;
                    }
                    if( OK )
                        continue;
                    for( int k = 0; k <26; ++k )
                    {
                        if( mat[j][k] > 0  && k != j )
                        {
                            p1 = mat[i][j];
                            p2 = mat[j][k];
                            OK = 2;
                            break;
                        }
                    }
                }
            }
            if( OK == 1 )
                break;
        }
        if( !OK )
            printf("%d\n-1 -1\n", cnt);
        else if( OK == 2 )
            printf("%d\n%d %d\n", cnt-1, p1, p2);
    }
    return 0;
} 
 C - Glass Carving 问在切割一个矩阵的过程中，最大小矩阵的面积是多少 
 首先确定，若某一个子矩阵的面积最大，那么这个矩阵的长和宽在所有的矩阵中，长和宽必定是里面最大的。那么只需要记录和更新矩阵的长和宽即可。可知每次切割矩阵的时候，必定是将某段子长（宽）切成两块，那么删除这段长度，并且同时更新两段新切割出的长度即可，最后输出最大长和宽之积即可 
  
 #include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define lson l, mid, rt <<1
#define rson mid + 1, r, rt <<1 | 1
#define pi acos(-1.0)
#define eps 1e-8
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 200010;

set  v, h;//记录切割的点
set  vv, hh;//记录长度
map  V, H;//记录长度的数量
set  :: iterator it, it1;
map  :: iterator mp1, mp2;
int n, m, q;

void init()
{
    V.clear();
    H.clear();
    v.clear();
    h.clear();
    vv.clear();
    hh.clear();
}

int main()
{
    while(~scanf("%d%d%d", &m, &n, &q))
    {
        init();
        v.insert(0);
        v.insert(m);
        h.insert(0);
        h.insert(n);
        V[m]++;
        H[n]++;
        hh.insert(n);
        vv.insert(m);
        while( q-- )
        {
            char op[10];
            int x;
            scanf("%s%d", op, &x);
            if( x == 0 )
                continue;
            if( op[0] == 'H' )
            {
                it1 = h.lower_bound(x);
                it = it1;
                it1--;
                //printf("between: %d %d\n", *it1, *it);
                h.insert(x);
                int xx = *it - *it1;
                //if( H.find( *it - *it1 ) != H.end() )
                //  H.erase( *it - *it1 );
                //H.insert( (*it - x) );
                //H.insert( (x - *it1) );
                if( H[xx] )
                    H[xx]--;
                if( !H[xx] )
                    hh.erase(xx);
                H[ *it - x ]++;
                H[ x - *it1 ]++;
                if( hh.find( *it-x ) == hh.end() )
                    hh.insert( *it - x );
                if( hh.find( x - *it1) == hh.end() )
                    hh.insert( x - *it1 );
            }
            else
            {
                it1 = v.lower_bound(x);
                it = it1;
                it1--;
                //printf("between: %d %d\n", *it1, *it);
                v.insert(x);
                int xx = *it - *it1;
                //if( V.find( *it - *it1 ) != V.end() )
                //  V.erase( *it - *it1 );
                //V.insert( (*it - x) );
                //V.insert( (x - *it1) );
                if( V[xx] )
                    V[xx]--;
                if( !V[xx] )
                    vv.erase(xx);
                V[ *it - x ]++;
                V[ x - *it1 ]++;
                if( vv.find( *it - x) == vv.end() )
                    vv.insert( *it - x );
                if( vv.find( x - *it1) == vv.end() )
                    vv.insert( x - *it1);
            }
            ll ans = (ll) *hh.rbegin() * (ll) *vv.rbegin();
            cout < 
 
 
 D - Clique Problem 给出n个点，每点有两个信息，wi, xi，其中两点满足(x1 - x2) >= w1 + w2，则两点可以连边。问最大的某个集合里面点的数量（集合里面任意两点都可相互到达）。 
 将x看成坐标轴上点的圆心，w看成该圆的半径，那么条件就转换为，若是坐标轴上两个圆相切或是相离，则认为两个圆可以连边。那么先对所以点排序，根据w+r升序。然后遍历所有的点，每次若是ri - wi > cur(当前最右距离),res++;同时更新最右的cur。 
  
 #include 
using namespace std;

const int N = 200010;

struct node{
	int x, r;
}a[N];

int cmp( const node &q, const node &w)
{
	return q.x + q.r = dis ){
				ans++;
				dis = max( dis, a[i].r + a[i].x );
			}
		}
		cout <

推荐阅读

go
Weight the Tree（树形dp）

题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅！－－－－－&# ... [详细]

蜡笔小新 2024-12-26 15:55:56
go
USACO 2014 Jan - Moolympics区间记录优化算法

题目描述：给定n个半开区间[a, b)，要求使用两个互不重叠的记录器，求最多可以记录多少个区间。解决方案采用贪心算法，通过排序和遍历实现最优解。 ... [详细]

蜡笔小新 2024-12-27 18:14:31
format
UNP 第9章：主机名与地址转换

本章探讨了用于在主机名和数值地址之间进行转换的函数，如gethostbyname和gethostbyaddr。此外，还介绍了getservbyname和getservbyport函数，用于在服务器名和端口号之间进行转换。 ... [详细]

蜡笔小新 2024-12-27 11:26:39
format
Codeforces Round #566 (Div. 2) A~F个人题解

Dashboard-CodeforcesRound#566(Div.2)-CodeforcesA.FillingShapes题意：给你一个的表格，你 ... [详细]

蜡笔小新 2024-12-25 18:41:21
join
深入理解线程局部存储

在多线程编程环境中，线程之间共享全局变量可能导致数据竞争和不一致性。为了解决这一问题，Linux提供了线程局部存储（TLS），使每个线程可以拥有独立的变量副本，确保线程间的数据隔离与安全。 ... [详细]

蜡笔小新 2024-12-25 17:04:36
go
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

学习链接：http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想，后期可以求解很 ... [详细]

蜡笔小新 2024-12-26 20:04:36
buffer
VxWorks中的双向链表与环形缓冲应用

本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法，通过具体示例代码加深理解。 ... [详细]

蜡笔小新 2024-12-26 13:26:16
list
Linux设备驱动程序：异步时间操作与调度机制

本文介绍了Linux内核中的几种异步延迟操作方法，包括内核定时器、tasklet机制和工作队列。这些机制允许在未来的某个时间点执行任务，而无需阻塞当前线程，从而提高系统的响应性和效率。 ... [详细]

蜡笔小新 2024-12-26 08:55:03
format
CUGB图论专题：排水系统中的最大流问题 - EK与Dinic算法解析

本题探讨如何通过最大流算法解决农场排水系统的设计问题。题目要求计算从水源点到汇合点的最大水流速率，使用经典的EK（Edmonds-Karp）和Dinic算法进行求解。 ... [详细]

蜡笔小新 2024-12-25 17:47:23
go
古代密码变换问题

本题探讨了一种字符串变换方法，旨在判断两个给定的字符串是否可以通过特定的字母替换和位置交换操作相互转换。核心在于找到这些变换中的不变量，从而确定转换的可能性。 ... [详细]

蜡笔小新 2024-12-28 09:18:22
go
分页插件3指定到某一页

前言--页数多了以后需要指定到某一页（只做了功能，样式没有细调）html ... [详细]

蜡笔小新 2024-12-27 15:19:01
go
组合数学问题：棋盘上的组合数计算

本文探讨了如何在模运算下高效计算组合数C(n, m)，并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元，从而实现除法取余的计算。 ... [详细]

蜡笔小新 2024-12-26 21:41:44
go
HTML Attribute Naming Conventions for Fast Components

This document outlines the recommended naming conventions for HTML attributes in Fast Components, focusing on readability and consistency with existing standards. ... [详细]

蜡笔小新 2024-12-26 19:13:45
go
文件描述符、文件句柄与打开文件之间的关联解析

本文详细探讨了文件描述符、文件句柄和打开文件之间的关系，通过具体示例解释了它们在操作系统中的作用及其相互影响。 ... [详细]

蜡笔小新 2024-12-26 14:00:46
c语言
C语言链表动态创建：头插法与尾插法详解

本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法，包括具体的实现代码和运行示例。通过这些内容，读者可以更好地理解和掌握链表的基本操作。 ... [详细]

蜡笔小新 2024-12-26 13:59:07

俺是胖墩墩_499

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章