CF 1538 G. Gift Set (贪心+思维)

简介: 【6月更文挑战第14天】

链接

题意:

Polycarp有x个红糖和y个蓝糖,现在他想用这些糖果做一些礼品盒(gift set),但规定每个礼品盒里必须有a个红糖、b个蓝糖或b个红糖、a个蓝糖。现在求他最多能做成多少个礼品盒。

分析:

首先我们会发现这个题有很多种方法:二分(O(log(n))),模拟(O(1)),模拟退火等,

二分:

既然他是最多能做多少,那么我们可以发现,答案满足单调性,那么我们直接二分答案就好了。
首先我们找到那个用的糖果更少,假设a的更少。那么我们枚举的答案,一定满足:$x-aans>=0;y-aans>=0;a=ba=ansb,abb-a$所以我们看有多少可以转化成b,如果比ans大或者相等那么这个ans是可以的,否则就不可以。

void solve(){
   
    scanf("%lld%lld%lld%lld", &n, &m, &a, &b);
    if(a>b) swap(a,b);
    ll l=0,r=1e9+7;
    while(l<r){
   
        ll mid=(l+r)/2;
        ll x=n,y=m;
        x-=a*mid;
        y-=a*mid;
        bool flag=(x>=0&&y>=0);
        if(b>a){
   ///防止出现a=b导致除以负数
            if(x/(b-a)+y/(b-a)<mid) flag=0;
        }
        if(flag) l=mid+1;
        else r=mid;
    }
    cout<<l-1<<endl;
}
AI 代码解读

模拟(O(1))

我们让n<m,a<b
我们分析出来他其实就是那么 一些(a+b,a+b)这样的二元组,和一些(a,b)这样的二元组。
我们发现我们选一个二元组(a,b)会让(n,m)之间的差缩减(b-a).所以我们可以先选mnba个(a,b)剩下的可以全选(a+b,a+b);

如果我们最后选完(a+b,a+b),还剩的够再买一个(a,b)或者(b,a)这样的二元组,那么我们就需要在做一次贡献。

需要特判一下,a=b因为不能除以0.答案是(na)

void solve()
{
   
    scanf("%lld%lld%lld%lld", &n, &m, &a, &b);    
    ///O(1)
    if(n>m) swap(n,m);
    if(a>b) swap(a,b);
    if(n<a||m<b) {
   
        puts("0");
        return ;
    }
    ll ca=m-n,cb=b-a;
    if(cb==0){
   
        printf("%lld\n",n/a);
        return;
    }
    ll num=min(ca/cb,min(n/a,m/b));
    n-=num*a;m-=num*b;
    ll ans=num+min(n,m)/(a+b)*2;
    if(n>=a&&m>=b) n-=a,m-=b,num++;
    printf("%lld\n",max(ans,num+min(n,m)/(a+b)*2));
}
AI 代码解读

链接

题意:

给出二维平面上的 n 个点,任意选择出三个点可以构成一个三角形,现在问满足下面条件的三角形的个数:

  • 三角形面积为整数
  • 三角形包含的(不包括边界)整数点为奇数
  • 其中所有坐标点的 xy 都是偶数

    分析:

    首先看下需要用到的定理之类的东西:
  1. 已知三角形三个点,求三角形面积
    S=x1(y2y3)+x2(y3y1)+x3(y1y2)2
  2. 皮克定理
    用于求多边形面积。S=a+b21其中a是多边形内部的整点数,b是多边形边界点数。S是多边形面积。边界上的点数为gcd(x1x2,y1y2)+1
// Problem: F1. Gregor and the Odd Cows (Easy)
// Contest: Codeforces - Codeforces Round #736 (Div. 2)
// URL: https://codeforces.com/contest/1549/problem/F1
// Memory Limit: 256 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

#define x first
#define y second
#define sf scanf
#define pf printf
#define PI acos(-1)
#define inf 0x3f3f3f3f
#define lowbit(x) ((-x)&x)
#define mem(a,x) memset(a,x,sizeof(a))
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
#define debug(x) cout << #x << ": " << x << endl;

const int MOD = 998244353;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;    
const int dx[] = {
   0, 1, -1, 0, 0};
const int dy[] = {
   0, 0, 0, 1, -1};
const int dz[] = {
   1, -1, 0, 0, 0, 0 };
int day[] = {
   0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

ll dp[2][2];

ll C(ll n,ll m){
   
    if(m==1) return n;
    else if(m==2)return n*(n-1)/2;
    else if(m==3) return (n-1)*(n-2)*n/6;
}

void solve()
{
   
    ll n;    
    scanf("%lld\n",&n);
    for(int i=1;i<=n;i++){
   
        int x, y;
        scanf("%d%d",&x,&y);
        dp[x%4/2][y%4/2]++;
    }
    ll ans=0;
    for(ll i=0;i<4;i++){
   
        for(ll j=i;j<4;j++){
   
            for(ll k=j;k<4;k++){
   
                ll x1=i/2,y1=i%2;
                ll x2=j/2,y2=j%2;
                ll x3=k/2,y3=k%2;
                ll sum=0;
                sum+=(x1==x2&&y1==y2);
                sum+=(x3==x2&&y3==y2);
                sum+=(x1==x3&&y1==y3);
                if(sum==0||sum==2) continue;
                if(i==j&&i==k) ans+=C(dp[x1][y1],3);
                else if(i==j) ans+=C(dp[x1][y1],2)*dp[x3][y3];
                else if(k==j) ans+=C(dp[x2][y2],2)*dp[x1][y1];
                else if(i==k) ans+=C(dp[x1][y1],2)*dp[x2][y2];
                else ans+=dp[x1][y1]*dp[x2][y2]*dp[x3][y3];
            }
        }
    }
    cout<<ans<<endl;
}

int main()
{
   
    ll t = 1;
    //scanf("%lld",&t);
    while(t--)
    {
   
        solve();
    }
    return 0;
}
AI 代码解读
iamzfh
+关注
目录
打赏
0
0
0
0
48
分享
相关文章
哈希表模拟封装unordered_map和unordered_set
哈希表模拟封装unordered_map和unordered_set
|
2月前
|
你对Collection中Set、List、Map理解?
你对Collection中Set、List、Map理解?
81 18
你对Collection中Set、List、Map理解?
只会“有序无序”?面试官嫌弃的List、Set、Map回答!
小米,一位热衷于技术分享的程序员,通过与朋友小林的对话,详细解析了Java面试中常见的List、Set、Map三者之间的区别,不仅涵盖了它们的基本特性,还深入探讨了各自的实现原理及应用场景,帮助面试者更好地准备相关问题。
74 20
【C++】map、set基本用法
本文介绍了C++ STL中的`map`和`set`两种关联容器。`map`用于存储键值对,每个键唯一;而`set`存储唯一元素,不包含值。两者均基于红黑树实现,支持高效的查找、插入和删除操作。文中详细列举了它们的构造方法、迭代器、容量检查、元素修改等常用接口,并简要对比了`map`与`set`的主要差异。此外,还介绍了允许重复元素的`multiset`和`multimap`。
65 3
【C++】map、set基本用法
【C++】unordered_map(set)
C++中的`unordered`容器(如`std::unordered_set`、`std::unordered_map`)基于哈希表实现,提供高效的查找、插入和删除操作。哈希表通过哈希函数将元素映射到特定的“桶”中,每个桶可存储一个或多个元素,以处理哈希冲突。主要组成部分包括哈希表、哈希函数、冲突处理机制、负载因子和再散列,以及迭代器。哈希函数用于计算元素的哈希值,冲突通过开链法解决,负载因子控制哈希表的扩展。迭代器支持遍历容器中的元素。`unordered_map`和`unordered_set`的插入、查找和删除操作在理想情况下时间复杂度为O(1),但在冲突较多时可能退化为O(n)。
39 5
|
5月前
|
【数据结构】map&set详解
本文详细介绍了Java集合框架中的Set系列和Map系列集合。Set系列包括HashSet(哈希表实现,无序且元素唯一)、LinkedHashSet(保持插入顺序的HashSet)、TreeSet(红黑树实现,自动排序)。Map系列为双列集合,键值一一对应,键不可重复,值可重复。文章还介绍了HashMap、LinkedHashMap、TreeMap的具体实现与应用场景,并提供了面试题示例,如随机链表复制、宝石与石头、前K个高频单词等问题的解决方案。
63 6
【数据结构】map&set详解
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中,Set 和 Map 用于存储唯一值和键值对,支持多种操作方法,如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象,有助于防止内存泄漏,适合特定场景使用。
|
4月前
|
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
60 1