首页 > 代码库 > UVA 10273 Eat or not to Eat?

UVA 10273 Eat or not to Eat?

直接暴力模拟 。以每次还未被删除的cnt[i]为一周期进行暴力模拟

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}int lcm(int a, int b) {if (a < b) swap(a,b);int tmp = gcd(a,b); return a / tmp * b;}#define MAXN 1010int N;int cnt[MAXN];int src[MAXN][20];bool killed[MAXN];int kill(int day){    int ans = 300,num = 0,st;    for (int i = 1; i <= N; i++)      if (!killed[i])      {          int val = src[i][day % cnt[i]];          if (val == ans) num++;          if (val < ans)          {              ans = val;              st = i;              num = 1;          }      }    if (num == 1) return st;    return 0;}int main(){    int T;    scanf("%d",&T);    while (T--)    {        scanf("%d",&N);        for (int i = 1; i <= N; i++)        {            scanf("%d",&cnt[i]);            for (int j = 1; j < cnt[i]; j++)                scanf("%d",&src[i][j]);            scanf("%d",&src[i][0]);        }        memset(killed,false,sizeof(killed));        int tot = 0, st = 1, ed,ans = 0;        while (true)        {            bool flag = false;            int tmp = 1;            for (int i = 1; i <= N; i++)               if (!killed[i]) tmp = lcm(tmp,cnt[i]);            ed = st + tmp - 1;            for (int i = st; i <= ed; i++)            {                int k = kill(i);                if (k)                {                    killed[k] = true;                    //printf("%d %d\n",k,i);                    tot ++;                    ans = i;                    flag = true;                }            }            st = ed + 1;            if (!flag || tot >= N) break;        }        printf("%d %d\n",N - tot,ans);    }    return 0;}

 

UVA 10273 Eat or not to Eat?