D:
/*贪心的 构造出来欧拉回路就是把度为3的点改一改方法是把4周的边隔一个扔一个这些扔掉的边一定要走两遍*/#include#include #include #define maxn 1010using namespace std;int n,m,ans;int main(){ scanf("%d%d",&n,&m);n--;m--; if(n==1){ ans=m*2+m+1+m-1; printf("%d\n",ans);return 0; } if(m==1){ ans=n*2+n+1+n-1; printf("%d\n",ans);return 0; } ans+=n/2; if(n&1)ans+=m/2; else ans+=(m+1)/2; if((n+m)&1){ ans+=(n+1)/2; if(n&1)ans+=(m+1)/2; else ans+=m/2; } else { ans+=n/2; if(n&1)ans+=m/2; else ans+=(m+1)/2; } ans+=n*(m+1)+m*(n+1); printf("%d\n",ans); return 0; }
I:
/*首先,肯定是用来打b的牌最后一块出 假设我们已经确定了有x张牌用来召唤怪兽那么对于一张牌 如果他用来打a那价值就是a如果它用来打b那价值就是b*x但是ab只能用一个 所以这种可以互相打破的价值不能用来做排序的key我们考虑 如果全都打b,那么总价值是固定的对于一张牌 改成打a 总价值+a-b*x 然后我们取 这个值前x大的 */ #include#include #include #include #define maxn 1010#define ll long longusing namespace std;ll n,now,sumb,Ans;struct node{ ll a,b;}r[maxn];ll cmp(const node &A,const node &B){ return (A.a-A.b*now)>(B.a-B.b*now);}int main(){ scanf("%lld",&n); for(ll i=1;i<=n;i++){ scanf("%lld%lld",&r[i].a,&r[i].b); sumb+=r[i].b; } for(now=1;now<=n;now++){ sort(r+1,r+1+n,cmp);ll s=0; for(ll i=1;i<=now;i++)s+=r[i].a-r[i].b*now; Ans=max(Ans,sumb*now+s); } printf("%lld\n",Ans); return 0;}
I:(div1)
/*对于div1 的数据 枚举x肯定是gg了然后就比较骚了div2的程序枚举x过程中 我们发下ans是先增后减大胆猜一发三分 */#include#include #include #include #define maxn 100010#define ll long longusing namespace std;ll n,now,sumb,Ans;struct node{ ll a,b;}r[maxn];ll cmp(const node &A,const node &B){ return (A.a-A.b*now)>(B.a-B.b*now);}ll Cal(ll x){ now=x;sort(r+1,r+1+n,cmp);ll s=0; for(ll i=1;i<=now;i++)s+=r[i].a-r[i].b*now; Ans=max(Ans,sumb*now+s);return sumb*now+s;}int main(){ scanf("%lld",&n); for(ll i=1;i<=n;i++){ scanf("%lld%lld",&r[i].a,&r[i].b); sumb+=r[i].b; } ll l=0,r=n,m1,m2,a1,a2; while(l<=r){ m1=(l+r)/2;m2=(m1+r)/2; a1=Cal(m1);a2=Cal(m2); if(a1>a2)r=m2-1; else l=m1+1; } printf("%lld\n",Ans); return 0;}