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 <

推荐阅读

main
VxWorks中的双向链表与环形缓冲应用

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

蜡笔小新 2024-12-26 13:26:16
main
USACO 2014 Jan - Moolympics区间记录优化算法

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

蜡笔小新 2024-12-27 18:14:31
main
Weight the Tree（树形dp）

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

蜡笔小新 2024-12-26 15:55:56
main
长春大学软件工程：二叉排序树实验报告

本实验主要探讨了二叉排序树（BST）的基本操作，包括创建、查找和删除节点。通过具体实例和代码实现，详细介绍了如何使用递归和非递归方法进行关键字查找，并展示了删除特定节点后的树结构变化。 ... [详细]

蜡笔小新 2024-12-26 15:32:56
main
C语言链表动态创建：头插法与尾插法详解

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

蜡笔小新 2024-12-26 13:59:07
main
深入理解KMP算法中的next数组：北大OJ 2406题解

本文详细探讨了KMP算法中next数组的构建及其应用，重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现，帮助读者更好地理解KMP算法的核心原理。 ... [详细]

蜡笔小新 2024-12-28 11:30:01
main
使用Objective-C和dispatch库实现并发素数计算

本文介绍如何使用Objective-C结合dispatch库进行并发编程，以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码，展示dispatch库的强大功能。 ... [详细]

蜡笔小新 2024-12-28 08:44:35
main
UNP 第9章：主机名与地址转换

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

蜡笔小新 2024-12-27 11:26:39
main
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

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

蜡笔小新 2024-12-26 20:04:36
main
golang常用库：配置文件解析库/管理工具viper使用

golang常用库：配置文件解析库管理工具-viper使用-一、viper简介viper配置管理解析库，是由大神SteveFrancia开发，他在google领导着golang的 ... [详细]

蜡笔小新 2024-12-28 13:47:52
main
Java 中 Writer flush()方法，示例

Java 中 Writer flush()方法，示例 ... [详细]

蜡笔小新 2024-12-28 06:41:52
substring
java编写的简易计算器

主要用了2个类来实现的，话不多说，直接看运行结果，然后在奉上源代码1.Index.javaimportjava.awt.Color;im ... [详细]

蜡笔小新 2024-12-27 18:18:10
main
寻找满足特定条件的整数N的最大和(a+b)

本文探讨了如何在给定整数N的情况下，找到两个不同的整数a和b，使得它们的和最大，并且满足特定的数学条件。 ... [详细]

蜡笔小新 2024-12-26 19:26:18
main
C++ 中的数组与动态数组初始化

本文探讨了 C++ 中普通数组和标准库类型 vector 的初始化方法。普通数组具有固定长度，而 vector 是一种可扩展的容器，允许动态调整大小。文章详细介绍了不同初始化方式及其应用场景，并提供了代码示例以加深理解。 ... [详细]

蜡笔小新 2024-12-26 15:38:03
main
文件描述符、文件句柄与打开文件之间的关联解析

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

蜡笔小新 2024-12-26 14:00:46

俺是胖墩墩_499

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

Tags | 热门标签

RankList | 热门文章