题目：
1.打牌
给定n个整数(n<=1000000),按照扑克牌对子（x，x）或者顺子（x，x+1，x+2）打出牌···问最多可以打出多少次对子或者顺子？牌的大小<=1000000
2.弹球
给定一个n*m的格子（n，m<=1000000000）,已知一个球从（1,1）处出发向左下方滚出··每次遇到边界则旋转90度反弹（类似与镜面反射）直到滚到一个角落停止···途中球每次经过一个方格则会将方格染色（包括第一个方格）,问只被染一次色的方格有多少个？
3.方盒子
已知有n个盒子（n<=200）,每个盒子有长宽···一个盒子可以放入一个长和宽都不小于它的盒子（可以不断嵌套）,一个盒子里只能套一层盒子例如1*2的盒子只能套一个1*1的盒子··而不能套两个··只能一个1*1的盒子套在另一个1*1的盒子里,套完后盒子的占地面积是套再最外面的盒子的面积之和··问最小占地面积是多少？
题解：
1.贪心
额··考试的时候脑子抽了··贪心贪错了··正解其实很简单··
如果某数字的牌小于2张直接出对子或者不出···如果大于3张的话我们可以考虑一直打对子直到只剩下一张或者两张··然后判断是否可以和之前两张牌打成顺子就可以了··因为对于打顺子这一次和打对子对答案的贡献是一样的··但打顺子的话我们会剩一张牌··这一张牌可能与后面的牌组成顺子从而对答案有多余贡献····
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+;
inline int R()
{
char c;int f=;
for(c=getchar();c<''||c>'';c=getchar());
for(;c<=''&&c>='';c=getchar()) f=(f<<)+(f<<)+c-'';
return f;
}
int n,maxx=,card[N];
int main()
{
//freopen("a.in","r",stdin);
n=R();int a;int ans=;
for(int i=;i<=n;i++) a=R(),card[a]++,maxx=max(maxx,a);
for(int i=;i<=maxx;i++)
{
if((card[i]&)&&(card[i+]&)&&(card[i+])) card[i]--,card[i+]--,card[i+]--,ans++;
ans+=card[i]/;
}
cout<<ans<<endl;
return ;
}
2.找规律
考试的时候看到这道题直接怂了····下来想想其实如果认真分析还是有可能做对的···哎····
具体过程由于我语文差实在用语言描述不出来··这里偷偷懒不写了··
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
inline long long R()
{
char c;long long f=;
for(c=getchar();c<''||c>'';c=getchar());
for(;c<=''&&c>='';c=getchar()) f=f*+c-'';
return f;
}
inline long long get(long long a,long long b)
{
if(b==) return a;
else return get(b,a%b);
}
int main()
{
//freopen("a.in","r",stdin);
int T;
long long a,b;
T=R();
while(T--)
{
a=R(),b=R();if(a<b) swap(a,b);
long long t=get(a-,b-);
long long s=(a-)*(b-)/t;
long long up=s/(b-);long long side=s/(a-);
cout<<s-(up-)*(side-)+<<endl;
}
return ;
}
3.二分图匹配+贪心/最大费用流
这道题还是比较容易想到的··
第一种方法是二分图匹配··左边的点向右边能够覆盖它的盒子连边···然后如果左边的盒子被匹配到了说明它被一个盒子覆盖了··因此想到我们要首先覆盖那些面积大的盒子··
所以在跑匈牙利算法时优先匹配那些面积大的盒子即可··
第二种方法其实和第一种本质是一样的··只是实现方式不同··和二分图一样每个盒子拆成左右两部分··建边方式和第一种一样··流量为1费用为左边盒子的面积··然后s向左边的点连流量为1费用为0的边··t向右边的点连流量飞1费用为0的边然后跑一边最大费用··用所有盒子的总面积减去最大费用（其实就是被覆盖的盒子的面积）就是答案
代码1：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=;
struct node
{
int x,y;
}bx[N];
inline int R()
{
char c;int f=;
for(c=getchar();c<''||c>'';c=getchar());
for(;c<=''&&c>='';c=getchar()) f=(f<<)+(f<<)+c-'';
return f;
}
int n,ed[N][N],ans,belon[N];
bool visit[N];
bool cmp(node a,node b)
{
return a.x*a.y<b.x*b.y;
}
inline bool get(int x)
{
for(int i=n;i>x;i--)
if(ed[x][i]&&!visit[i])
{
visit[i]=true;
if(belon[i]==||get(belon[i]))
{
belon[i]=x;return true;
}
}
return false;
}
int main()
{
//freopen("box.in","r",stdin);
//freopen("box.out","w",stdout);
n=R();
for(int i=;i<=n;i++) bx[i].x=R(),bx[i].y=R();
sort(bx+,bx+n+,cmp);
for(int i=;i<=n;i++)
{
ans+=bx[i].x*bx[i].y;
for(int j=i+;j<=n;j++)
if(bx[j].x>=bx[i].x&&bx[j].y>=bx[i].y) ed[i][j]=true;
}
for(int i=n-;i>=;i--)
{
memset(visit,false,sizeof(visit));
if(get(i)) ans-=bx[i].x*bx[i].y;
}
cout<<ans<<endl;
return ;
}
代码2：注意memset时附上的值不能为负数
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
queue<int>que;
const int N=;
const int inf=0x3f3f3f3f;
int first[N],next[N],go[N],cost[N],rest[N],tot=;
int dis[N];
bool visit[N],work[N];
struct node
{
int x,y;
inline friend bool operator == (node a,node b)
{
return a.x==b.x&&a.y==b.y;
}
}bx[N];
inline int R()
{
char c;int f=;
for(c=getchar();c<''||c>'';c=getchar());
for(;c<=''&&c>='';c=getchar()) f=(f<<)+(f<<)+c-'';
return f;
}
int n,src,des,ans;
inline void comb(int a,int b,int v,int w)
{
next[++tot]=first[a],first[a]=tot,go[tot]=b,rest[tot]=v,cost[tot]=w;
next[++tot]=first[b],first[b]=tot,go[tot]=a,rest[tot]=,cost[tot]=-w;
}
inline bool cmp(node a,node b)
{
if(a.x*a.y==b.x*b.y) return a.x<b.x;
else return a.x*a.y<b.x*b.y;
}
inline bool SPFA()
{
for(int i=;i<=des;i++)dis[i]=-inf;
memset(work,false,sizeof(work));
while(!que.empty())que.pop();
que.push(src),dis[src]=;
int u,v,e;
while(!que.empty())
{
u=que.front(),que.pop();
visit[u]=false;
for(e=first[u];e;e=next[e])
{
if(rest[e]>&&dis[u]+cost[e]>dis[v=go[e]])
{
dis[v]=dis[u]+cost[e];
if(!visit[v])
{
visit[v]=true;
que.push(v);
}
}
}
}
return dis[des]!=-inf;
}
inline int dinic(int u,int flow)
{
if(u==des)
{
ans+=flow*dis[des];
return flow;
}
work[u]=true;
int v,e,res=,delta;
for(e=first[u];e;e=next[e])
{
if(!work[v=go[e]]&&rest[e]>&&dis[u]+cost[e]==dis[v])
{
delta=dinic(v,min(rest[e],flow-res));
if(delta)
{
rest[e]-=delta,rest[e^]+=delta;
res+=delta;if(res==flow) break;
}
}
}
return res;
}
inline void getmax()
{
while(SPFA())
dinic(src,1e+);
}
int main()
{
//freopen("a.in","r",stdin);
n=R();src=,des=*n+;int sum=;
for(int i=;i<=n;i++) bx[i].x=R(),bx[i].y=R();
sort(bx+,bx+n+,cmp);
n=unique(bx+,bx+n+)-bx-;
for(int i=;i<=n;i++)
{
sum+=bx[i].x*bx[i].y;
for(int j=i+;j<=n;j++)
if(bx[j].x>=bx[i].x&&bx[j].y>=bx[i].y) comb(j,i+n,,bx[i].x*bx[i].y);
}
for(int i=;i<=n;i++) comb(src,i,,);
for(int i=;i<=n;i++) comb(i+n,des,,);
getmax();
cout<<sum-ans<<endl;
return ;
}