4062-4065

zxhdsg · 2023-03-15 17:13:06 · 个人记录

A

#include <bits/stdc++.h>
#define Maxn 10000 + 5
using namespace std;
vector <short> vec[Maxn];
bool vi[5010];
signed main()
{
    int i,j,n,k,q,x,w;
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>k>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        for(j=1;j<=x;j++)   cin>>w,vec[i].push_back(w);
    }
    cin>>q;
    while(q--)
    {
        memset(vi,0,sizeof(vi));
        cin>>x;
        for(i=1;i<=x;i++)
        {
            cin>>w;
            for(j=0;j<vec[w].size();j++)    vi[vec[w][j]]=true;
        }
        for(i=1;i<=k;i++)   if(vi[i])   cout<<i<<" ";
        cout<<endl;
    }
    return 0;
} 

#include<bits/stdc++.h>
using namespace std;
bitset<5010>s[10010],s1;
int k,a,b,n,bi,ki,q,ni;
int main(){
    //freopen("10.in","r",stdin);
    //freopen("10.out","w",stdout);
    scanf("%d%d",&k,&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&b);
        for(int j=1;j<=b;j++){
            scanf("%d",&ki);
            s[i][ki]=1;
        }
    }

    scanf("%d",&q);

    for(int i=1;i<=q;i++){
        scanf("%d",&a);
        for(int j=1;j<=a;j++){
            scanf("%d",&ni);
            s1=s1|s[ni];
        }

        for(int j=1;j<=k;j++){
            if(s1[j])printf("%d ",j);
        }
            printf("\n");

        s1.reset();
    }

    return 0;
}

B

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n,t,p,q,l,r,k,minn=1e9,maxn=0;
int a[N];
bool check(int m)
{
    minn=1e9,maxn=0;
    int c=1;
    for(int i=p;i<=q;i++)
    {
        minn=min(a[i],minn);    maxn=max(maxn,a[i]);
        if (maxn-minn>m)    c++,minn=a[i],maxn=a[i];
    }
    if (c<=k)   return true;
    else    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);     cout.tie(0);
    cin>>n>>t;
    for(int i=1;i<=n;i++)   
    {
        cin>>a[i];
        minn=min(a[i],minn);    maxn=max(maxn,a[i]);
    }
    int flag=maxn-minn;
    while (t--)
    {
        cin>>p>>q>>k;
        l=0,r=flag;
        int mid;
        while (l<r)
        {
            int mid=(l+r)/2;
            if (check(mid)) r=mid;
            else    l=mid+1;
        }
        cout<<r<<endl;
    }
    return 0;
}

C

#include <bits/stdc++.h>
using namespace std;
const int N = 2000 + 5;
int a[N][N]={0};
bool vi[200]={0};
string t;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n,i,j,ans=0;
    cin>>t;
    n=t.length();
    if(n>2000){cout<<"known,next.";return 0;}
    for(i=0;i<n;i++)
    {
        memset(vi,0,sizeof(vi));
        for(j=i;j<n;j++)
        {
            if(!vi[t[j]])   a[i][j]=a[i][j-1]+1;
            else            a[i][j]=a[i][j-1];
            vi[t[j]]=true;
        }
    }
    for(i=1;i<n;i++)
        for(j=i+1;j<n;j++)
            ans=max(ans,a[0][i]*a[i+1][j]*a[j+1][n-1]);     
    cout<<ans;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
string t;
bool vi[200],vit[200];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n,m,i,j,tl,l,sum,ans=0,cnt;
    cin>>t; n=t.length();
    for(i=1;i<=26;i++)
    {
        memset(vi,0,sizeof(vi));
        for(cnt=0,tl=0;tl<n&&cnt<i;tl++)
            if(!vi[t[tl]])
                cnt++,vi[t[tl]]=true;
        if(cnt<i)   break;
        for(j=1;j<=26;j++)
        {
            memset(vit,0,sizeof(vit));
            for(cnt=0,l=tl;l<n&&cnt<j;l++)
                if(!vit[t[l]])
                    cnt++,vit[t[l]]=true;   
            if(cnt<j)   break;

            memset(vit,0,sizeof(vit));
            for(cnt=0;l<n;l++)
                if(!vit[t[l]])
                    cnt++,vit[t[l]]=true;
            ans=max(ans,i*j*cnt);
        }
    }
    cout<<ans;      
    return 0;
}

D

#include<bits/stdc++.h>
using namespace std;
int T,n[110],m[110];
int h[1010][1010][110];
int xi[110],yi[110];
int xt[4]={1,-1,0,0};
int yt[4]={0,0,1,-1};
bool bl[1010][1010][110];
struct node{
    int x,y;
    int w;
    bool operator < (const node &a)const{
        return a.w<w;
    }
};
priority_queue<node,vector<node>,less<node> >p[110];
inline int _abs(int a,int b){
    return a>b?a-b:b-a;
}
void bfs(int t){
    node temp;
    while(!p[t].empty()){
        temp=p[t].top();
        p[t].pop();
        if(bl[temp.x][temp.y][t])continue;
        bl[temp.x][temp.y][t]=1;
        if(temp.x==xi[t]&&temp.y==yi[t]){
            printf("%d\n",temp.w);
            return ;
        }
        for(int i=0;i<4;i++){
            node temp1;
            temp1.x=temp.x+xt[i];
            temp1.y=temp.y+yt[i];
            if(temp1.x>0&&temp1.x<=n[t]){
                if(temp1.y>0&&temp1.y<=m[t]){
                    if(!bl[temp1.x][temp1.y][t]){
                        temp1.w=temp.w+_abs(h[temp.x][temp.y][t],h[temp1.x][temp1.y][t])+1;
                        p[t].push(temp1);
                    }
                }
            }
        }
    }
}
int main(){
    scanf("%d",&T);
    for(int i=0;i<T;i++){
        scanf("%d%d",&n[i],&m[i]);
        for(int i1=1;i1<=n[i];i1++){
            for(int j1=1;j1<=m[i];j1++){
                scanf("%d",&h[i1][j1][i]);
            }
        }
        scanf("%d%d",&xi[i],&yi[i]);
        p[i].push((node){xi[i],yi[i],0});
        scanf("%d%d",&xi[i],&yi[i]);
    }
    for(int i=0;i<T;i++){
        bfs(i);
    }
    return 0;
}