USACO15OPEN Bessie Goes Moo

发表于 | 分类于 |
字数统计: 333 字

题目地址

题解

大力枚举…
单纯从经验上来说，这道题有背包的解法，但是讨论极其复杂，还不如套一堆循环。
注意负数的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
//1B2E2S1I GOES 1M2O
ll ans=0,cnt[7][7]={0};
int n,mp[256];
void init(){
    n=read();
    mp['B']=0,mp['E']=1,mp['S']=2,
    mp['I']=3,mp['G']=4,mp['O']=5,
    mp['M']=6;
    char ord[3];
    ll u;
    for(int i=1;i<=n;i++){
        scanf("%s%lld",ord,&u);
        cnt[mp[ord[0]]][(u%7+7)%7]++;
    }
}
void solve(){
    ll t1,t2,t3;
    for(int A=0;A<7;A++)
        for(int B=0;B<7;B++)
            for(int C=0;C<7;C++)
                for(int D=0;D<7;D++)
                    for(int E=0;E<7;E++)
                        for(int F=0;F<7;F++)
                            for(int G=0;G<7;G++){
                                t1=A+B+B+C+C+D,t2=B+C+E+F,t3=G+F+F;
                                if(t1%7==0||t2%7==0||t3%7==0)
                                    ans+=cnt[0][A]*cnt[1][B]*cnt[2][C]*cnt[3][D]
                                    *cnt[4][E]*cnt[5][F]*cnt[6][G];
                            }
    printf("%lld\n",ans);
}
int main(){
    init();
    solve();
    return 0;
}