AtCoder Beginner Contest 173（E 思维模拟 F 容斥 思维题 ）ccsudeer-

题目链接

自从第一次打了AT 差一题AK，后面的AT 总是差两题，唉。。好菜啊

E – Multiplication 4

题意：给你n个数，要求选出k个值 使得k个值得乘积最大。

做法：记得做过类似得题，也是超出long long  求乘积最大，好像是用了log 判断大小。但这里有负数 就不太好搞了。

做法参考来自：博客

思路感觉很对，但是他代码交。wa在了 after_contest_01.txt， 大概就是被hack了。想了半天感觉没什么问题啊，不知道为什么wa了。

 

经过几番研究 ，终于发现了 坑点，感谢网友提供的数据：

7 5
35 25 5 -25 -25 -25 -25

答案应该是13671875

所以 这里的坑点就是  当能凑到正数情况  且 当k为奇数时  先取正数最大的，再考虑正数与负数两两乘积最大

 

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const ll mod=1e9+7; const int N=2e5+10; ll a[N],n,k; vector<ll>G1,G2; bool cmp2(ll x,ll y) {     return abs(x)<abs(y); } bool cmp1(ll x,ll y) {     return x>y; } bool cmp3(ll x,ll y) {     return x<y; } void run1() {     //puts("***");     sort(G1.begin(),G1.end(),cmp1);     sort(G2.begin(),G2.end(),cmp3); //    for(ll v:G1) printf("%lld ",v);puts(""); //    for(ll v:G2) printf("%lld ",v);puts("");      int id1=0,id2=0;     ll ans=1;     if(k%2){         ans=G1[id1++];     }     while(id1+1<G1.size()&&id2+1<G2.size()&&id1+id2+2<=k){         //printf("id1:%d id2:%dn",id1,id2);          if(G1[id1]*G1[id1+1]>G2[id2]*G2[id2+1]){             ans=ans*G1[id1]%mod*G1[id1+1]%mod;             id1+=2;         }         else{             ans=ans*G2[id2]%mod*G2[id2+1]%mod;             id2+=2;         }     }     //printf("id1:%d id2:%d sz:%dn",id1,id2,G1.size());      while(id2+1<G2.size()&&id1+id2+2<=k){         ans=ans*G2[id2]%mod*G2[id2+1]%mod;         id2+=2;     }     while(id1+1<G1.size()&&id1+id2+2<=k){         ans=ans*G1[id1]%mod*G1[id1+1]%mod;         id1+=2;     }     //if(id1+id2<k) ans=ans*G1[id1++]%mod;     printf("%lldn",(ans+mod)%mod);  } int main() {     n=read(),k=read();     int zero=0;     rep(i,1,n)     {         a[i]=read();         if(a[i]>0) G1.emplace_back(a[i]);         else if(a[i]<0) G2.emplace_back(a[i]);         else zero++;     }     if(G2.size()-(G2.size()&1)+G1.size()>=k&&(k&1)<=G1.size()){         run1();     }     else if(zero){         puts("0");     }     else{         sort(a+1,a+1+n,cmp2);         ll ans=1;         rep(i,1,k) ans=ans*a[i]%mod;         printf("%lldn",(ans+mod)%mod);     }  }  /* 7 5 35 25 5 -25 -25 -25 -25 */ 

F – Intervals on Tree

题意:看了半天都没怎么懂的题意。大概就是 枚举l、r  然后集合包括[l,r]内的数。问集合内的联通块是多少，并求和输出。

做法：参考来自:博客

很妙的做法。。。容斥的方法

 #include<bits/stdc++.h> using namespace std;  int n;  int main(){      ios::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);      cin>>n;     long long ans=0;     for(int i=1;i<=n;i++){         ans+=(long long)(n-i+1)*i;     }     for(int i=1;i<n;i++){         int a,b;         cin>>a>>b;         if(a>b)swap(a,b);         ans-=(long long)a*(n-b+1);     }     cout<<ans<<endl;      return 0; }