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 <

推荐阅读

数组
Weight the Tree（树形dp）

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

蜡笔小新 2024-12-26 15:55:56
数组
古代密码变换问题

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

蜡笔小新 2024-12-28 09:18:22
io
USACO 2014 Jan - Moolympics区间记录优化算法

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

蜡笔小新 2024-12-27 18:14:31
io
扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]

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

蜡笔小新 2024-12-26 20:04:36
io
使用动态规划算法求解0-1背包问题

本文介绍如何利用动态规划算法解决经典的0-1背包问题。通过具体实例和代码实现，详细解释了在给定容量的背包中选择若干物品以最大化总价值的过程。 ... [详细]

蜡笔小新 2024-12-27 19:17:15
io
词根词缀解析：greg、hap、helio及其他词源故事

本文基于刘洪波老师的《英文词根词缀精讲》，深入探讨了多个重要词根词缀的起源及其相关词汇，帮助读者更好地理解和记忆英语单词。 ... [详细]

蜡笔小新 2024-12-27 18:59:50
io
Java并发编程：LinkedBlockingQueue的实际应用

本文介绍了Java并发库中的阻塞队列（BlockingQueue）及其典型应用场景。通过具体实例，展示了如何利用LinkedBlockingQueue实现线程间高效、安全的数据传递，并结合线程池和原子类优化性能。 ... [详细]

蜡笔小新 2024-12-27 18:51:49
version
使用 Azure Service Principal 和 Microsoft Graph API 获取 AAD 用户列表

本文介绍了一段通用代码示例，该代码不仅能够操作 Azure Active Directory (AAD)，还可以通过 Azure Service Principal 的授权访问和管理 Azure 订阅资源。Azure 的架构可以分为两个层级：AAD 和 Subscription。 ... [详细]

蜡笔小新 2024-12-27 16:07:12
io
Apache Jena 中 Txn.executeWrite 方法详解与代码示例

本文详细介绍了 Apache Jena 库中的 Txn.executeWrite 方法，通过多个实际代码示例展示了其在不同场景下的应用，帮助开发者更好地理解和使用该方法。 ... [详细]

蜡笔小新 2024-12-26 17:55:52
io
优化ListView性能

本文深入探讨了如何通过多种技术手段优化ListView的性能，包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]

蜡笔小新 2024-12-28 10:36:30
io
Handling Null Object Encoding in OAuth 1.0a API Implementation

Explore a common issue encountered when implementing an OAuth 1.0a API, specifically the inability to encode null objects and how to resolve it. ... [详细]

蜡笔小新 2024-12-28 08:54:34
python
技术分享：从动态网站提取站点密钥的解决方案

本文探讨了如何从动态网站中提取站点密钥，特别是针对验证码（reCAPTCHA）的处理方法。通过结合Selenium和requests库，提供了详细的代码示例和优化建议。 ... [详细]

蜡笔小新 2024-12-28 04:11:47
io
Java 中的 BigDecimal pow()方法，示例

Java 中的 BigDecimal pow()方法，示例 ... [详细]

蜡笔小新 2024-12-27 20:54:03
tree
新浪笔试题

1:有如下一段程序：packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]

蜡笔小新 2024-12-27 19:32:17
数组
Java面试题解析

本文详细介绍了Java编程语言中的核心概念和常见面试问题，包括集合类、数据结构、线程处理、Java虚拟机（JVM）、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题，帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]

蜡笔小新 2024-12-27 13:55:14

俺是胖墩墩_499

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

Tags | 热门标签

RankList | 热门文章