2/13 qaq~~贪心+二位前缀和+数论(求多个数的最大公因数)

二维前缀和
https://www.luogu.com.cn/problem/P1369

#include 

using namespace std;
const int maxn=5005;
int n,mp[maxn][maxn],mx=-1,my=-1,tmp;
int go(int x,int y,int xx,int yy)         //划定矩形区间的累加和
{
    if(x>=xx||y>=yy)
        return 0;
    return mp[xx][yy]-mp[xx][y-1]-mp[x-1][yy]+mp[x-1][y-1];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(x>mx)
            mx=x;
        if(y>my)
            my=y;
        mp[x][y]=1;
    }
    for(int i=1;i<=mx;i++)                     //二维前缀和的构造
    {
        for(int j=1;j<=my;j++)
            mp[i][j]=mp[i][j]+mp[i-1][j]+mp[i][j-1]-mp[i-1][j-1];
    }
    for(int i=1;i<=mx;i++)
    {
        for(int j=1;j<=my;j++)
        {
            for(int ii=2;ii<=mx;ii++)
            {
                for(int jj=2;jj<=my;jj++)
                {
                    if(i>=ii||j>=jj)
                        continue;
                    int num=go(i,j,ii,jj);
                    num-=go(i+1,j+1,ii-1,jj-1);
                    tmp=max(tmp,num);
                }
            }
        }
    }
    cout< 
数论(求多个数的最大公因数)
 1.记录每个数的因子出现的次数
 2.这个次数表示它是多少个数的因子
 3.从最大的数递减输出，数越大，那它作为因子的次数就越少
 
#include 

using namespace std;
const int maxn=1e4+5;;
int n,k,c[maxn];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x;scanf("%d",&x);
        k=max(k,x);
        int m=sqrt(x);
        for(int i=1;i<=m;i++)
        {
            if(x%i==0)
            {
                c[i]++;
                if(x!=i*i)
                    c[x/i]++;
            }
        }
    }
    //c[i]中含义为：是几个数的最大公因数
    for(int i=1;i<=n;i++)
	{
        while(c[k] 
https://www.luogu.com.cn/problem/P1230
 
#include 

using namespace std;
const int maxn=1005;
struct node
{
    int id,val;
}e[maxn];
int w,n;
bool vis[maxn];
bool cmp(node e1,node e2)
{
    return e1.val>e2.val;
}

int main()
{
    scanf("%d%d",&w,&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&e[i].id);
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&e[i].val);
    }
    sort(e+1,e+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        int fg=0;
        if(!vis[e[i].id])
        {
            vis[e[i].id]=1;
            continue;
        }
        else
        {
            for(int j=e[i].id;j>=1;j--)
            {
                if(!vis[j])
                {
                    vis[j]=1;
                    fg=1;
                    break;
                }
            }
            if(fg)
                continue;
            w-=e[i].val;
        }
    }
    cout< 
P1056 [NOIP2008 普及组] 排座椅
 https://www.luogu.com.cn/problem/P1056
 
#include 
using namespace std;
const int maxn=2005;
int m,n,k,l,d;
struct xx
{
    int id,val;
}e[maxn],e1[maxn];

bool cmp1(xx e1,xx e2)
{
    return e1.val>e2.val;
}
bool cmp2(xx e1,xx e2)
{
    return e1.id 
https://www.luogu.com.cn/problem/P1233
 愚蠢的忘记更新木棍的长度了。。。。qaq
 
#include 

using namespace std;
const int maxn=5005;
struct node
{
    int l,w;
}e[maxn];
int n;
bool vis[maxn];
bool cmp(node e1,node e2)
{
    if(e1.l==e2.l) return e1.w>e2.w;
    return e1.l>e2.l;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&e[i].l,&e[i].w);
    sort(e+1,e+n+1,cmp);
    int ans=0,x,y;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            ans++;
            vis[i]=1;
            x=e[i].l;y=e[i].w;
            for(int j=i+1;j<=n;j++)
            {
                if(!vis[j]&&e[j].l<=x&&e[j].w<=y)
                {
                    vis[j]=1;
                    x=e[j].l;
                    y=e[j].w;
                }
            }
        }
    }
    cout< 
https://www.luogu.com.cn/problem/P1095
 从每秒结束的角度惊醒考虑，思路会更清晰，还有就是能闪则闪，记得更新s1的距离
 
#include 

using namespace std;
const int maxn=50005;
int m,s,t;

int main()
{
    scanf("%d%d%d",&m,&s,&t);
    int s1=0,s2=0;
    for(int i=1;i<=t;i++)
    {
        s1+=17;
        if(m>=10)
        {
            m-=10;
            s2+=60;
        }
        else
            m+=4;
        if(s2>s1)
            s1=s2;
        if(s1>s)
        {
            cout<<"Yes"< 
一道贼烦的时间模拟题（年 月 日 时 分+判断闰年）
 https://www.luogu.com.cn/problem/P1167
 
#include 

using namespace std;
const int maxn=5005;
int n,a[maxn],st[10],ed[10],num;
int m2[15]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int m1[15]={0,31,29,31,30,31,30,31,31,30,31,30,31};
bool check(int year)
{
    if((year%4==0&&year%400!=0)||year%400==0)
        return 1;
    return 0;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    scanf("%d-%d-%d-%d:%d",&st[1],&st[2],&st[3],&st[4],&st[5]);
    scanf("%d-%d-%d-%d:%d",&ed[1],&ed[2],&ed[3],&ed[4],&ed[5]);
    int time=0;
    for(int i=st[1];i=a[i])
        {
            time-=a[i];
            num++;
        }
        else
            break;
    }
    cout<