2/13 qaq~~ greed + binary prefix sum + number theory (find the greatest common factor of multiple numbers)

Two dimensional prefixes and
https://www.luogu.com.cn/problem/P1369

#include <bits/stdc++.h>

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)         // Define the cumulative sum of rectangular intervals 
{
    
    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++)                     // Construction of two-dimensional prefix sum 
    {
    
        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<<tmp<<endl;
    return 0;
}

number theory ( Find the greatest common factor of multiple numbers )
1. Record the number of times the factor of each number appears
2. This number represents the factor of how many numbers it is
3. Decrease the output from the maximum number , The bigger the number , The fewer times it is used as a factor

#include <bits/stdc++.h>

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] Means ： Is the greatest common factor of several numbers 
    for(int i=1;i<=n;i++)
	{
    
        while(c[k]<i) 
            k--;
        cout<<k<<endl;
    }
    return 0;
}

https://www.luogu.com.cn/problem/P1230

#include <bits/stdc++.h>

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<<w<<endl;
    return 0;
}

P1056 [NOIP2008 Popularization group ] Row seats
https://www.luogu.com.cn/problem/P1056

#include <bits/stdc++.h>
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<e2.id;
}
int main()
{
    
    scanf("%d%d%d%d%d",&m,&n,&k,&l,&d);
    for(int i=1;i<=d;i++)
    {
    
        int x1,y1,x2,y2;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        if(x1==x2)   // A vertical bar 
        {
    
            e[min(y1,y2)].id=min(y1,y2);e[min(y1,y2)].val++;
        }
        else if(y1==y2)  // Horizontal line 
        {
    
            e1[min(x1,x2)].id=min(x1,x2);e1[min(x1,x2)].val++;
        }
    }
    sort(e1+1,e1+m+1,cmp1);
    sort(e1+1,e1+k+1,cmp2);
    for(int i=1;i<=k;i++)
        cout<<e1[i].id<<" ";
    cout<<endl;

    sort(e+1,e+n+1,cmp1);
    sort(e+1,e+l+1,cmp2);
    for(int i=1;i<=l;i++)
        cout<<e[i].id<<" ";
    cout<<endl;

    return 0;
}

https://www.luogu.com.cn/problem/P1233
Stupid forgot to update the length of the stick ....qaq

#include <bits/stdc++.h>

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<<ans<<endl;
    return 0;
}

https://www.luogu.com.cn/problem/P1095
Wake up and think from the perspective of the end of each second , The thinking will be clearer , And if you can flash, then flash , Remember to update s1 Distance of

#include <bits/stdc++.h>

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"<<endl;
            cout<<i<<endl;return 0;
        }
    }
    cout<<"No"<<endl<<s1<<endl;
    return 0;
}

A thief annoying time simulation problem （ year month Japan when branch + Judgement of leap year ）
https://www.luogu.com.cn/problem/P1167

#include <bits/stdc++.h>

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<ed[1];i++)  // year 
    {
    
        if(check(i))
          time+=366;
        else
            time+=365;
    }
    if(check(st[1]))  // Judge the starting year 
    {
    
        for(int i=1;i<st[2];i++)   // Subtract the months with more statistics （ Starting year ）
            time-=m1[i];
    }
    else
    {
    
        for(int i=1;i<st[2];i++)
            time-=m2[i];
    }

    if(check(ed[1]))  // Judge the ending year 
    {
    
        for(int i=1;i<ed[2];i++)  // Add the months that are not counted （ Year of termination ）
            time+=m1[i];
    }
    else
    {
    
        for(int i=1;i<ed[2];i++)
            time+=m2[i];
    }

    for(int i=1;i<st[3];i++)  // Subtract the number of days counted （ Starting year ）
        time--;
    for(int i=1;i<ed[3];i++)  // Add the number of days not counted （ Year of termination ）
        time++;
    time=time*24*60;
    time-=(st[4]*60+st[5]);
    time+=(ed[4]*60+ed[5]);
    
    for(int i=1;i<=n;i++)
    {
    
        if(time>=a[i])
        {
    
            time-=a[i];
            num++;
        }
        else
            break;
    }
    cout<<num<<endl;
    return 0;
}