A
签到(a-b problem 不用贴了吧, 以后 atcoder 小于 300 分题均不贴代码)
B
发现选择的 p,q 一定是其中两点间的距离, 于是可以 O(n2)枚举两点, 再 O(n2)判断, 其实可以做到 O(n3)不过 O(n4)就够了.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- int n,ans;
- ll x[52],y[52];
- int main()
- {
- scanf("%d",&n);
- ans=n;
- for(int i=1;i<=n;i++)scanf("%lld%lld",&x[i],&y[i]);
- for(int i=1;i<n;i++)
- for(int j=i+1;j<=n;j++)
- {
- ll dx=x[i]-x[j],dy=y[i]-y[j];
- int sum=0;
- for(int k=1;k<=n;k++)
- {
- int flag=1;
- for(int l=1;l<=n;l++)if(x[k]-x[l]==dx&&y[k]-y[l]==dy){flag=0;break;}
- sum+=flag;
- }
- ans=min(ans,sum);
- }
- printf("%d\n",ans);
- }
- View Code
- C
按照从小到大排成 a1,a2,...,an, 分类讨论: 1, 只有两个数直接相减. 2, 对于全是正的, 显然应该先拿 a1 的减去除了 an 以外其他数, 再用 an 减去该数, 显然答案就是 a2+a3+...+an-a1. 对于全是负的, 可以采用类似的方法. 3, 对于有正有负的, 显然选出 a1 和 an,a1 减去除 an 外的正数, an 减去除 a1 外的负数, 再 an-a1 即可, 答案就是所有数的绝对值
- #include<bits/stdc++.h>
- using namespace std;
- const int N=1e5+7;
- int n,m,a[N],ax[N],ay[N];
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)scanf("%d",&a[i]);
- sort(a+1,a+n+1);
- if(n==2)
- {
- printf("%d\n%d %d\n",a[2]-a[1],a[2],a[1]);
- return 0;
- }
- if(a[1]>=0)
- {
- for(int i=2;i<n;i++)ax[++m]=a[1],ay[m]=a[i],a[1]-=a[i];
- ax[++m]=a[n],ay[m]=a[1],a[n]-=a[1];
- printf("%d\n",a[n]);
- for(int i=1;i<=m;i++)printf("%d %d\n",ax[i],ay[i]);
- return 0;
- }
- if(a[n]<=0)
- {
- int ans=a[n];
- for(int i=1;i<n;i++)ans-=a[i];
- printf("%d\n",ans);
- for(int i=1;i<n;i++)printf("%d %d\n",a[n],a[i]),a[n]-=a[i];
- return 0;
- }
- int pos=0;
- for(int i=1;i<=n;i++)if(a[i]>=0){pos=i;break;}
- for(int i=2;i<pos;i++)ax[++m]=a[n],ay[m]=a[i],a[n]-=a[i];
- for(int i=pos;i<n;i++)ax[++m]=a[1],ay[m]=a[i],a[1]-=a[i];
- ax[++m]=a[n],ay[m]=a[1],a[n]-=a[1];
- printf("%d\n",a[n]);
- for(int i=1;i<=m;i++)printf("%d %d\n",ax[i],ay[i]);
- }
- View Code
- D
发现只会做两轮交易, A->B,B->A, 然后发现是个完全背包 DP, 并且第二次背包的容量是 O(n2)的, 于是就可以直接 O(n2)DP 结束了, 感觉这个 D 比 C 简单吧.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N=5005;
- int n,m,a[3],b[3];
- ll ans,f[N*N];
- int main()
- {
- scanf("%d",&n);
- for(int i=0;i<3;i++)scanf("%d",&a[i]);
- for(int i=0;i<3;i++)scanf("%d",&b[i]);
- for(int i=0;i<3;i++)
- if(b[i]>a[i])
- for(int j=a[i];j<=n;j++)
- f[j]=max(f[j],f[j-a[i]]+b[i]-a[i]);
- for(int i=0;i<=n;i++)m=max(1ll*m,f[i]),f[i]=0;
- m+=n;
- for(int i=0;i<3;i++)
- if(a[i]>b[i])
- for(int j=b[i];j<=m;j++)
- f[j]=max(f[j],f[j-b[i]]+a[i]-b[i]);
- for(int i=0;i<=m;i++)ans=max(ans,f[i]);
- ans+=m;
- printf("%lld",ans);
- }
- View Code
- E
考后 5min 写出来, 简直自闭...... 早知道不去写 F 的打表程序还没跑出来...... 就是每次移动总是 min->max, 然后 f[i]表示 max 为 i 时的方案数, 显然对于多个 max 的可以变换成 x! 种 (x 为 max 的人数), 然后求一个阶乘前缀和即可. 注意最后 f[n] 不要求.
- #include<bits/stdc++.h>
- #define lson l,mid,rt<<1
- #define rson mid+1,r,rt<<1|1
- using namespace std;
- const int N=1e6+7,mod=1e9+7;
- int n,d,h,f[N],fac[N],inv[N],sf[N],s[N<<2];
- int qpow(int a,int b)
- {
- int ret=1;
- while(b)
- {
- if(b&1)ret=1ll*ret*a%mod;
- a=1ll*a*a%mod,b>>=1;
- }
- return ret;
- }
- void update(int k,int v,int l,int r,int rt)
- {
- if(l==r){s[rt]=v;return;}
- int mid=l+r>>1;
- if(k<=mid)update(k,v,lson);
- else update(k,v,rson);
- s[rt]=(s[rt<<1]+s[rt<<1|1])%mod;
- }
- int query(int L,int R,int l,int r,int rt)
- {
- if(L<=l&&r<=R)return s[rt];
- int mid=l+r>>1,ret=0;
- if(L<=mid)ret+=query(L,R,lson);
- if(R>mid)ret+=query(L,R,rson);
- return ret%mod;
- }
- int main()
- {
- scanf("%d%d%d",&n,&h,&d);
- fac[0]=1;for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
- for(int i=1;i<=n;i++)sf[i]=(sf[i-1]+fac[i])%mod;
- update(0,fac[n],0,h,1);
- for(int i=1;i<=h;i++)
- {
- f[i]=query(max(0,i-d),i-1,0,h,1);
- if(i<h)f[i]=1ll*f[i]*sf[n]%mod,update(i,f[i],0,h,1);
- }
- printf("%d",f[h]);
- }
- View Code
- F
好吧, 看了网上程序, 差不多是构造个近似 fib 数列的玩意, 把表抄上也没管了......
- #include<bits/stdc++.h>
- using namespace std;
- long long a1[13]={1,2,4,7,12,20,29,38,52,101},a2[13]={1,2,4,7,12,20,30,39,67,101};
- long long n,w=1,mp[15][15];
- int main()
- {
- cin>>n;
- for(int i=1;i<=n;i++)mp[i][i]=0;
- for(int i=1;i<=n;i++)
- {
- for(int j=i+1;j<=n;j++)mp[i][j]=mp[j][i]=w*a1[j-i-1];
- w*=a2[n-i];
- }
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=n;j++)cout<<mp[i][j]<<' ';
- cout<<endl;
- }
- }
- View Code
result:rank101 rating+=58, 精准地没进前 100......
来源: http://www.bubuko.com/infodetail-3093836.html