传送门

G.Game SET

题意

每张牌有4个属性，每个属性共有3个属性值（若属性值为*，则代表为该属性的任一属性值）
现有n张牌，给出对应的属性及其属性值，任选3张，满足这3张的4种属性对应的属性值，要么完全相同，要么完全不同.若存在解，输出3张牌的序号；若不存在解，输出-1.

思路

脑残解法
状压dp
用一个12位的二进制表示当前选择的牌组成的每个属性中包含了哪些值。
但很显然单纯的状压的复杂度有1e9级别。
把由一副牌，二副牌，三副牌可以组成的合法状态预处理出来，大概有1500个，依旧会T。
不用求出所有的状态是否能达到，只要搜索到一种ok的组合就直接输出即可。
场上思路混乱，写成了状压dp，下面的代码是状压dp
正确解法
暴力枚举2张牌，可以直接得出第3张牌的4个属性值，判是否存在即可

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=5e3+10;
const int M=2e6+10;
int dp[4][N],pre[4][N];
int pow2[20],m;
char s[270][10];
char s1[100];
int id,val[7];
vector<int>vt[4];
bool vis[5][N],ok[5][N];
void print(int i,int x){
    if(i==0)return;
    print(i-1,pre[i][x]);
    printf("%d",dp[i][x]);
    if(i<3)putchar(' ');
}
bool pp=0;
int ans=0;
void dfs(int i,int now){
    if(pp)return;
    if(i==4){
        for(int j=2;j>=0;j--)
            for(auto it:vt[j]){
                if(ok[j+1][it|now]==0)continue;
                if(vis[j+1][it|now])continue;
                if(vis[j][it]){
                    dp[j+1][it|now]=id;
                    pre[j+1][it|now]=it;
                }
                if(j==2&&vis[j][it]){
                    ans=(it|now);
                    pp=1;
                    return;
                }
            }
        return;
    }

    if(val[i]==-1){
        dfs(i+1,now+pow2[i*3]);
        dfs(i+1,now+pow2[i*3+1]);
        dfs(i+1,now+pow2[i*3+2]);
    }else dfs(i+1,now+val[i]);
}
void init()
{
    for(int i=0;i<m;i++){
        int x=i;
        int num[4]={0};
        int now=0;
        while(x){
            int y=x&1;
            num[now/3]+=y;
            now++;x>>=1;
        }
        bool f=1;
        for(int j=0;j<4;j++){
            if(num[j]==0||num[j]==2){
                f=0;break;
            }
        }
        if(f)vt[3].push_back(i),ok[3][i]=1;

        f=1;
        for(int j=0;j<4;j++){
            if(num[j]>1||num[j]==0){
                f=0;break;
            }
        }
        if(f)vt[1].push_back(i),ok[1][i]=1;

        f=1;
        for(int j=0;j<4;j++){
            if(num[j]>2||num[j]==0){
                f=0;break;
            }
        }
        if(f)vt[2].push_back(i),ok[2][i]=1;
    }
    vt[0].push_back(0);
}
int main()
{
    int t;scanf("%d",&t);
    pow2[0]=1;int cas=0;
    for(int i=1;i<=20;i++)pow2[i]=pow2[i-1]*2;
    m=1<<12;
    init();
    //for(int i=1;i<=3;i++)cout<<vt[i].size()<<endl;
    while(t--){
        pp=0;
        for(int j=0;j<=3;j++)
            for(auto it:vt[j])
            dp[j][it]=vis[j][it]=pre[j][it]=0;

        dp[0][0]=vis[0][0]=1;

        //memset(s,0,sizeof s);
        //memset(s1,0,sizeof s1);

        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf(" %s",s1);
            int len=strlen(s1);
            int now=0;
            for(int j=0;j<len;j++){
                if(s1[j]=='['){
                    if(s1[j+1]=='*')s[i][now]='*';
                    else s[i][now]=s1[j+2];
                    now++;
                }
            }
        }
        printf("Case #%d: ",++cas);
        for(int i=1;i<=n;i++){
            id=i;
            memset(val,0,sizeof val);
            if(s[i][0]=='n')val[0]+=pow2[0];
            else if(s[i][0]=='w')val[0]+=pow2[1];
            else if(s[i][0]=='h')val[0]+=pow2[2];
            else val[0]=-1;

            if(s[i][1]=='i')val[1]+=pow2[3];
            else if(s[i][1]=='q')val[1]+=pow2[4];
            else if(s[i][1]=='v')val[1]+=pow2[5];
            else val[1]=-1;

            if(s[i][2]=='o')val[2]+=pow2[6];
            else if(s[i][2]=='t')val[2]+=pow2[7];
            else if(s[i][2]=='p')val[2]+=pow2[8];
            else val[2]=-1;

            if(s[i][3]=='e')val[3]+=pow2[9];
            else if(s[i][3]=='r')val[3]+=pow2[10];
            else if(s[i][3]=='u')val[3]+=pow2[11];
            else val[3]=-1;

            dfs(0,0);
            if(pp){
                print(3,ans);
                break;
            }
            for(int j=1;j<=3;j++)
                for(auto it:vt[j])
                if(dp[j][it])vis[j][it]=1;
        }

        if(!pp)puts("-1");
        else putchar('\n');
    }
}

I.Interesting Computer Game

题意

有n对数$\lbrace a_i, b_i \rbrace$,每次操作可以从一对数$\lbrace a_i, b_i \rbrace$中选择一个数。求最多可以选择多少个不同的数。
$1\leq T \leq 10, 1 \leq a_i \leq 10^9, 1 \leq b_i \leq 10^9$

思路

观察发现，如果把所有给出的a,b组合连边，在环上的点必定都可以全部选择。所以进行拓扑排序，只有当一个点在拓扑排序的过程中度数变为0才需要在答案上减去1。
前期一直在用二分图写，T飞

代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=5e5+10;
const int M=2e6+10;
const int INF=0x3f3f3f3f;
int head[N],cnt,n,nn,tot,num1[N],in[N];
struct edge{
     int next,to;
}e[M];
void add(int u,int v){
     e[++cnt].next=head[u];
     e[cnt].to=v;
     head[u]=cnt;
}
void init(){
    cnt=tot=0;
}
struct node{
    int y1,y2;
}q[N];
queue<int>que;
int main()
{
     int T;cin>>T;
     int cas=0;
     while(T--){
          init();
          while(!que.empty())que.pop();
          scanf("%d",&n);
          for(int i=1;i<=n;i++){
              int x,t;scanf("%d %d",&t,&x);
              q[i]={t,x};
              num1[++tot]=x;
              num1[++tot]=t;
          }
          sort(num1+1,num1+tot+1);
          nn=unique(num1+1,num1+tot+1)-num1-1;
          for(int i=0;i<=nn;i++)in[i]=head[i]=0;
          for(int i=1;i<=n;i++){
              int y1=q[i].y1,y2=q[i].y2;
              y1=lower_bound(num1+1,num1+nn+1,y1)-num1;
              y2=lower_bound(num1+1,num1+nn+1,y2)-num1;
              add(y1,y2);add(y2,y1);
              in[y1]++;in[y2]++;
          }
          int ans=nn;
          for(int i=1;i<=nn;i++){
              if(in[i]==1)que.push(i);
          }
          while(!que.empty()){
                int u=que.front();que.pop();
                if(in[u]==0)continue;
                in[u]--;
                for(int i=head[u];i;i=e[i].next){
                    int v=e[i].to;
                    if(in[v]<=0)continue;
                    in[v]--;
                    if(in[v]==0)ans--;
                    if(in[v]==1)que.push(v);
                }
          }
          printf("Case #%d: %d\n",++cas,ans);
     }
}

K.Kabaleo Lite

题意

有n种食物，每种食物的利润为a[i],数量为b[i],其中利润可以为负。每个客人若吃了第k种食物，则必须吃1~k-1食物，且每种只能吃一个。求在满足最多客人数量的情况下，可以获得的最大利润。
$1\leq T \leq 10, 1 \leq n \leq 10^{5}, -10^{9} \leq a_{i} \leq 10^{9}, 1 \leq b_{i} \leq 10^{5}$

思路

对利润维护一遍前缀和，每次求满足数量条件的前缀最大值，求得后将对应前缀数量-1
注意：爆long long, 采用__int128

代码

#include <bits/stdc++.h>

using namespace std;

#define int __int128

// typedef long long ll.;

const int N = 1e5 + 10;

void scan(__int128 &x)//输入
{
    x = 0;
    int f = 1;
    char ch;
    if((ch = getchar()) == '-') f = -f;
    else x = x*10 + ch-'0';
    while((ch = getchar()) >= '0' && ch <= '9')
        x = x*10 + ch-'0';
    x *= f;
}
void _print(__int128 x)
{
    if(x > 9) _print(x/10);
    putchar(x%10 + '0');
}
void print(__int128 x)//输出
{
    if(x < 0)
    {
        x = -x;
        putchar('-');
    }
    _print(x);
}

__int128 t, n;
__int128 a[N], b[N];
__int128 pos[N];

__int128 pre[N], f[N][20];
__int128 Log[N]; 
void RMQ_pre(__int128 n)
{
    Log[0] = -1;
    for (int i = 1; i <= n; i++)
    {
        if (!(i & (i - 1))) Log[i] = Log[i - 1] + 1;
        else Log[i] = Log[i - 1];
        f[i][0] = pre[i];
    }
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
__int128 RMQ_min(__int128 l, __int128 r)
{
    __int128 d = Log[r - l + 1];
    return max(f[l][d], f[r - (1 << d) + 1][d]);
}

signed main()
{
    __int128 cas = 0;
    scan(t);
    // scanf("%d", &t);
    while (t--)
    {
        scan(n);
        // scanf("%d", &n);
        for (int i = 1; i <= n; i++)
        {
            __int128 num;
            scan(num);
            a[i] = num;
        }

        for (int i = 1; i <= n; i++)
        {
            __int128 num;
            scan(num);
            b[i] = num;
        }

        for (int i = 0; i <= 100000; i++) pos[i] = n + 1;
        for (int i = 1; i <= n; i++)
            if (pos[b[i]] == n + 1) pos[b[i]] = min(pos[b[i]], i);

        pre[0] = 0;
        for (int i = 1; i <= 100000; i++) pre[i] = pre[i - 1] + a[i];


        RMQ_pre(n);

        __int128 ans = 0;
        __int128 wz = n;
        for (int i = 1; i <= b[1]; i++)
        {
            wz = min(wz, pos[i - 1] - 1);
            ans += RMQ_min(1, wz);
        }
        printf("Case #%d: ", ++cas);
        print(b[1]);
        printf(" ");
        print(ans);
        printf("\n");
        // printf("Case #%d: %lld %lld\n", ++cas, b[1], ans);
    }
}