第八周 10.18-10.24

10.18

sb了。copy后忘改一个数字。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 LL a[100];
 7 
 8 int main(void)
 9 {
10     int T; cin>>T;
11     while(T--)
12     {
13         int N; scanf("%d",&N);
14         int p=0,n=0;
15         for(int i=0;i<N;i++)
16         {
17             scanf("%I64d",a+i);
18             if(a[i]>0) p++;
19             else if(a[i]<0) n++;
20         }
21         sort(a,a+N);
22         LL ans;
23         if(p==0&&n<2) ans=a[N-1];
24         else
25         {
26             if(p)
27             {
28                 ans=a[N-1];
29                 for(int i=N-2;i>=0;i--) if(a[i]>0) ans*=a[i];
30                 for(int i=0;i<N-2;i++) if(a[i]<0&&a[i+1]<0)
31                 {
32                     ans*=a[i]*a[i+1]; i++;
33                 }
34             }
35             else
36             {
37                 ans=a[0]*a[1];
38                 for(int i=2;i<N-1;i++) if(a[i]<0&&a[i+1]<0)
39                 {
40                     ans*=a[i]*a[i+1]; i++;
41                 }
42             }
43         }
44         printf("%I64d
",ans);
45     }
46     return 0;
47 }

Aguin

HDU 5505 GT and numbers

没筛表T死。文霸筛还是挺好用。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 typedef unsigned long long ull;
 7 const int maxn=1e6;
 8 int pr[maxn];
 9 
10 void GetPrime(void)
11 {
12     memset(pr,0,sizeof(pr));
13     for(int i=2;i<=maxn;i++)
14     {
15         if(!pr[i]) pr[++pr[0]]=i;
16         for(int j=1;j<=pr[0]&&pr[j]*i<=maxn;j++)
17         {
18             pr[i*pr[j]]=1;
19             if(i%pr[j]==0) break;
20         }
21     }
22     return;
23 }
24 
25 int main(void)
26 {
27     GetPrime();
28     int T; cin>>T;
29     while(T--)
30     {
31         ull N,M;
32         scanf("%I64u%I64u",&N,&M);
33         int ans=0;
34         for(int i=1;i<=pr[0];i++)
35         {
36             if(pr[i]>min(M,N)) break;
37             int t1=0,t2=0;
38             if(N%pr[i]==0) while(N%pr[i]==0) {t1++; N/=pr[i];}
39             if(M%pr[i]==0) while(M%pr[i]==0) {t2++; M/=pr[i];}
40             if(!t1&&t2||t1&&!t2) {ans=-1;break;}
41             while((1<<ans)*t1<t2) ans++;
42         }
43         if(M!=1||N!=1) ans=-1;
44         printf("%d
",ans);
45     }
46     return 0;
47 }

Aguin

HDU 5506 GT and set

就是暴。赛时想起STL有求交。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <set>
 5 using namespace std;
 6 set<int> ss[30];
 7 set<int> S[5];
 8 int N,L;
 9 
10 bool dfs(int pos)
11 {
12     if(pos>=N) return true;
13     set<int> tmp;
14     for(int i=0;i<L;i++)
15     {
16         tmp=S[i];
17         if(S[i].empty()) S[i]=ss[pos];
18         else
19         {
20             set<int> in; in.clear();
21             set_intersection(S[i].begin(),S[i].end(),ss[pos].begin(),ss[pos].end(),inserter(in,in.begin()));
22             if(in.empty()) {S[i]=tmp;continue;}
23             S[i]=in;
24         }
25         if(dfs(pos+1)) return true;
26         S[i]=tmp;
27     }
28     return false;
29 }
30 
31 int main(void)
32 {
33     int T; cin>>T;
34     while(T--)
35     {
36         scanf("%d%d",&N,&L);
37         for(int i=0;i<L;i++) S[i].clear();
38         for(int i=0;i<N;i++)
39         {
40             int sz; scanf("%d",&sz);
41             ss[i].clear();
42             for(int j=0;j<sz;j++)
43             {
44                 int x; scanf("%d",&x);
45                 ss[i].insert(x);
46             }
47         }
48         puts(dfs(0)?"YES":"NO");
49     }
50     return 0;
51 }

Aguin

10.19-10.24

似乎什么都没干？