A
签到, 开 long long(不开也 pp 不了)
- #include<bits/stdc++.h>
- using namespace std;
- long long a,b,ans;
- int main()
- {
- cin>>a>>b>>ans;ans*=2;
- if(a==b)ans+=a*2;
- else ans+=min(a,b)*2+1;
- cout<<ans;
- }
- View Code
- B
two-pointer, 注意特判 n<=k||m<=k 的情况, 因为这个还 WA 了一发真是自闭(不然就翻掉 Gaozijian 了)
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int N=2e5+7;
- int n,m,k;
- ll ans,ta,tb,a[N],b[N];
- int main()
- {
- scanf("%d%d%I64d%I64d%d",&n,&m,&ta,&tb,&k);
- for(int i=1;i<=n;i++)scanf("%I64d",&a[i]);
- for(int i=1;i<=m;i++)scanf("%I64d",&b[i]);
- if(n<=k||m<=k){puts("-1");return 0;}
- for(int i=0,p=0;i<=k;i++)
- {
- while(p<m&&a[i+1]+ta>b[p+1])p++;
- if(p+k-i>=m){puts("-1");return 0;}
- ans=max(ans,b[p+k-i+1]+tb);
- }
- cout<<ans;
- }
- View Code
- C
构造, 发现每个位置总能和 1/n 中的一个位置交换, 考虑前 (i-1) 个数已经排好序了, 这时候考虑第 i 个数, 记第 i 个数的位置为 pos, 当 pos!=i 时(pos=i 直接跳过不管了), 有以下四种情况: 1,2(pos-i)>=n, 直接交换. 2,2(n-pos)>=n, 这个先交换 pos 和 n, 再交换 i 和 n.3,2(i-1)>=n, 这个依次交换(1,pos),(1,i),(1,pos).4, 其余的情况, 这个依次交换(1,pos),(1,n),(i,n),(1,pos). 大力讨论一波即可.
- #include<bits/stdc++.h>
- using namespace std;
- const int N=3e5+7;
- int n,pos,num,a[N],b[N],ax[N*5],ay[N*5];
- void Swap(int x,int y)
- {
- ax[++num]=x,ay[num]=y;
- int p=a[x],q=a[y];
- swap(a[x],a[y]);
- swap(b[p],b[q]);
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[a[i]]=i;
- for(int i=1;i<=n;i++)
- if(b[i]!=i)
- {
- pos=b[i];
- if(2*(b[i]-i)>=n)Swap(i,b[i]);
- else if(2*(n-b[i])>=n)Swap(pos,n),Swap(i,n);
- else if(2*(i-1)>=n)Swap(1,pos),Swap(1,i),Swap(1,pos);
- else Swap(1,pos),Swap(1,n),Swap(i,n),Swap(1,pos);
- }
- printf("%d\n",num);
- for(int i=1;i<=num;i++)printf("%d %d\n",ax[i],ay[i]);
- }
- View Code
- D
签到, 排序.
- #include<bits/stdc++.h>
- using namespace std;
- const int N=3e5+7;
- struct node{int a,b,id;}a[N],b[N];
- int n,n1,n2,ans,an[N];
- bool cmp(node a,node b){return a.b<b.b;}
- int main()
- {
- scanf("%d",&n);
- for(int i=1,x,y;i<=n;i++)
- {
- scanf("%d%d",&x,&y);
- if(x<y)a[++n1]=(node){x,y,i};
- else b[++n2]=(node){x,y,i};
- }
- if(n1>=n2)
- {
- sort(a+1,a+n1+1,cmp);
- printf("%d\n",n1);
- for(int i=n1;i;i--)printf("%d",a[i].id);
- }
- else{
- sort(b+1,b+n2+1,cmp);
- printf("%d\n",n2);
- for(int i=1;i<=n2;i++)printf("%d",b[i].id);
- }
- }
- View Code
- E
首先若位置坐标和不同直接 puts("NO"). 然后先找到每个石子的相对位置, 理性分析一波发现能够不改变相对位置交换, 否则就无解. 具体的就是把石子分成向右移动和向左移动两种, 记录距离, 然后直接前面和前面匹配, 后面和后面匹配, 直接模拟这个过程, 发现位置上会发生交叉也是 puts("NO").
- #include<bits/stdc++.h>
- using namespace std;
- const int N=3e5+7;
- typedef long long ll;
- struct node{ll d;int id;}a[N],a1[N],a2[N];
- int n,n1,n2,num,ai[N*5],aj[N*5];
- ll s1,s2,b[N],ad[N*5];
- bool cmp(node a,node b){return a.d<b.d;}
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)scanf("%I64d",&a[i].d),s1+=a[i].d,a[i].id=i;
- for(int i=1;i<=n;i++)scanf("%I64d",&b[i]),s2+=b[i];
- if(s1!=s2){puts("NO");return 0;}
- sort(a+1,a+n+1,cmp);
- sort(b+1,b+n+1);
- for(int i=1;i<=n;i++)
- if(a[i].d<b[i])a1[++n1]=(node){b[i]-a[i].d,i};
- else if(a[i].d>b[i])a2[++n2]=(node){a[i].d-b[i],i};
- for(int i=1,j=1;i<=n1;i++)
- {
- ll res=a1[i].d;
- while(res)
- {
- if(a1[i].id>a2[j].id){puts("NO");return 0;}
- if(res<a2[j].d)ai[++num]=a[a1[i].id].id,aj[num]=a[a2[j].id].id,ad[num]=res,a2[j].d-=res,res=0;
- else ai[++num]=a[a1[i].id].id,aj[num]=a[a2[j].id].id,ad[num]=a2[j].d,res-=a2[j].d,j++;
- }
- }
- puts("YES");
- printf("%d\n",num);
- for(int i=1;i<=num;i++)printf("%d %d %I64d\n",ai[i],aj[i],ad[i]);
- }
- View Code
- F
听说随机能过? 后来又说随机基本都 FST 了. 看到了一种非随机的解法: 每个数先按照最低的非零位排序, 然后按位处理, 对于每一位, 仅考虑当前位选 0/1 造成的影响, 选择偏小的那种即可.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<ll,ll>pii;
- int n;
- ll sum,ans;
- vector<pii>a[80];
- int getbit(ll x)
- {
- int ret=0;
- while(x)
- {
- if(x&1)return ret;
- ret++,x>>=1;
- }
- }
- int count(ll x)
- {
- int ret=0;
- while(x)ret+=x&1,x>>=1;
- return ret;
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- ll v,x;cin>>v>>x,sum+=v;
- a[getbit(x)].push_back(pii(v,x));
- }
- for(int i=62;~i;i--)
- if(a[i].size())
- {
- ll s0=0,s1=0;
- for(int j=0;j<a[i].size();j++)
- if(count(a[i][j].second&ans)&1)s1+=a[i][j].first;
- else s0+=a[i][j].first;
- if(sum>0&&s0>s1||sum<0&&s0<s1)ans+=1ll<<i;
- }
- cout<<ans;
- }
- View Code
- GH
不会, 告辞.
result: 终于用大号 lintoto 打了, rank97,rating+=113,now_rating=2267, 超了小号 hfctf0210 的 2210(大号的原来的 max_rating 也是 2210)啦! div1+2 终于进前 100 啦! 不过这次是由于 E 和 F FST 了一大片 (不过本身 F 放随机过也实在是不合理) 才涨了这么多 rating, 不过感觉这场把签到题都切了怎么都能涨吧.
吐槽一下不知道为啥 cf C 和 E 全部给 5n,C 只要 4n 就行, E 只要 n 就行, 4n+n=5n 刚好用一半 2333, 什么垃圾构造题.
好像还抽到 T-shirt 了?
来源: http://www.bubuko.com/infodetail-3080053.html