链接
题意：
Polycarp有x个红糖和y个蓝糖，现在他想用这些糖果做一些礼品盒（gift set），但规定每个礼品盒里必须有a个红糖、b个蓝糖或b个红糖、a个蓝糖。现在求他最多能做成多少个礼品盒。
分析：
首先我们会发现这个题有很多种方法：二分($O(log(n))$)，模拟($O(1)$),模拟退火等，
二分：
既然他是最多能做多少，那么我们可以发现，答案满足单调性，那么我们直接二分答案就好了。
首先我们找到那个用的糖果更少，假设a的更少。那么我们枚举的答案，一定满足：$x-aans>=0;y-aans>=0;$这是肯定的，因为如果用的少的都不满足跟不用提多的了，然后我们看如果$a=b$那么他一定是满足条件的，否则就是$a=ans$这样就是满足条件的，否则不满足。为什么那？其实就是用剩下的空变化一下成b,由a变成b需要加上$b-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;
}
模拟($O(1)$)
我们让n<m,a<b
我们分析出来他其实就是那么 一些(a+b,a+b)这样的二元组，和一些(a,b)这样的二元组。
我们发现我们选一个二元组(a,b)会让(n,m)之间的差缩减(b-a).所以我们可以先选$\frac{m-n}{b-a}$个(a,b)剩下的可以全选(a+b,a+b);
如果我们最后选完(a+b,a+b)，还剩的够再买一个(a,b)或者(b,a)这样的二元组，那么我们就需要在做一次贡献。
需要特判一下,a=b因为不能除以0.答案是($\frac{n}{a}$)
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));
}
链接
题意：
给出二维平面上的 $n$ 个点，任意选择出三个点可以构成一个三角形，现在问满足下面条件的三角形的个数：
- 三角形面积为整数
- 三角形包含的（不包括边界）整数点为奇数
- 其中所有坐标点的 $x$ 和 $y$ 都是偶数
分析：
首先看下需要用到的定理之类的东西：
- 已知三角形三个点，求三角形面积
$S=\frac{x_1(y_2-y_3)+x_2(y_3-y_1)+x_3(y_1-y_2)}{2}$ - 皮克定理
用于求多边形面积。$S=a+\frac{b}{2}-1$其中a是多边形内部的整点数，b是多边形边界点数。S是多边形面积。边界上的点数为$gcd(x_1-x_2,y_1-y_2)+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;
}
