HZNU 2019 Summer training 1

HZNU 2019 Summer training 1"/>

HZNU 2019 Summer training 1

A - Alex and a Rhombus　　

CodeForces - 1180A 

水：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<math.h>
using namespace std;
#define ll long longconst int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;void chongfu(){}
int main()
{ll n;scanf("%lld",&n);ll tmp = 2 * n - 1;printf("%lld\n",tmp + (tmp - 1) * (tmp - 1) / 2);}

View Code

 

B - Nick and Array　　　　

CodeForces - 1180B 

题意：给一个长度为n的数列，对于数列中的每一个数ai都可以选择把它变为-ai-1，求所构成的最大乘积

题解：对于绝对值来说的话，正数变负数的绝对值会变大，负数变正数的绝对值会变小，所以要尽可能的把数字都调为负数，但如果有奇数个数的话，要保留一个正数确保积为正

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<math.h>
using namespace std;
#define ll long longconst int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;int a[maxn];
int main()
{int n;int ling = 0;scanf("%d",&n);int zero = 0;int maxx = -INF;for(int i=0;i<n;i++){scanf("%d",&a[i]);if(a[i] == 0)zero ++;int tmp;if(a[i] < 0)tmp = -1 * a[i] - 1;elsetmp = a[i];if(tmp > maxx)maxx = tmp;}if(n % 2 == 1 and zero == n){for(int i=0;i<n;i++)printf("%d ",a[i]);}else if(n % 2 == 0){for(int i=0;i<n;i++)printf("%d ",a[i] >= 0 ? -1 * a[i] - 1 : a[i]);}else if(n % 2 == 1){for(int i=0;i<n;i++){int tmp = a[i] > 0 ? a[i] : -1 * a[i] - 1;if(tmp == maxx) {printf("%d ", tmp);maxx = INF;}elseprintf("%d ",a[i] >= 0 ? -1 * a[i] - 1 : a[i]);}}}

View Code

 

C - Valeriy and Deque

CodeForces - 1180C 

题意：n个数放双端队列里面，有一个操作：取出前两个数，大的数放前面，小的或者一样大的放后面，问你经过m次操作后的前两个数是什么。 题解：使用deque进行模拟，当地一个数字是最大值的时候可以发现，之后的每次都会把第二个放在队尾，然后n - 1次循环。可以预先处理所有的出现的情况，之后输出

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<math.h>
#include<queue>
#include<deque>
using namespace std;
#define ll long longconst int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;int a[maxn];
int n,q;
deque<int>que;vector<pair<int,int>> v1;
vector<pair<int,int>> v2;
int main()
{scanf("%d %d",&n,&q);int maxx = -INF;for(int i=0;i<n;i++){scanf("%d",&a[i]);que.push_back(a[i]);maxx = max(maxx,a[i]);}while(que[0] != maxx){int tmp1 = que[0];int tmp2 = que[1];que.pop_front();que.pop_front();if(tmp1 < tmp2){que.push_front(tmp2);que.push_back(tmp1);}else{que.push_back(tmp2);que.push_front(tmp1);}v1.push_back({tmp1,tmp2});}int len1 = v1.size();n--;int len2 = n;while(n--){int tmp1 = que[0];int tmp2 = que[1];que.pop_front();que.pop_front();if(tmp1 < tmp2){que.push_front(tmp2);que.push_back(tmp1);}else{que.push_back(tmp2);que.push_front(tmp1);}v2.push_back({tmp1,tmp2});}while(q--){ll m;scanf("%lld",&m);if(m <= len1){printf("%d %d\n",v1[m-1].first,v1[m-1].second);}else{m -= len1;m %= len2;if(m == 0)printf("%d %d\n",v2[len2-1].first,v2[len2-1].second);elseprintf("%d %d\n",v2[m-1].first,v2[m-1].second);}}
}

View Code

 

D - Tolik and His Uncle

 CodeForces - 1180D 

题意：n * m的网格中，起点为(1,1)，每次寻找一个dx，dy，然后从当前的(x,y)跳到(x + dx, y + dy)，保证每次的dx和dy不与之前的相等。要求跳完所有的格子，求跳的顺序

题解：反复从头到尾跳，再从尾到头跳 (1,1)→(n,m)→(1,2)→(n,m−1)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<math.h>
#include<queue>
#include<deque>
using namespace std;
#define ll long longconst int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;vector<pair<int,int>>v;
int main()
{int n,m;scanf("%d %d",&n,&m);for(int i=1;i<=n;i++) {for (int j = 1; j <= m; j++) {v.push_back({i, j});}}int i=0,j = v.size()-1;int tot = 0;while(true){printf("%d %d\n",v[i].first,v[i].second);tot++;i++;if(tot == n * m)break;printf("%d %d\n",v[j].first,v[j].second);tot++;j--;if(tot == n * m)break;}
}

View Code

 

E - Serge and Dining Room（线段树）

 CodeForces - 1180E

题意：给出a 和 b 数组，a为各种食物的价格，b为一列排着队的小朋友拥有的钱，小朋友排队购买食物，每个人都买自己能买的起的最贵的食物，买不起就离开队伍。给出q次操作，操作1是修改食物的价格，操作2是修改小朋友的钱，每次操作后询问当小朋友买完之后，能买到的最贵的食物的价格是多少，没有食物了就输出-1.

题解：直接拿kk的题解写法：

首先，小朋友的顺序对最终答案没有任何影响，因为如果两个小朋友能买两个东西，这两个小朋友无论怎么换，都是能买的了的。

　　其次，对于一个价格为x的物品，如果有一个钱大于等于x的小朋友，就可以买走这个物品。如果我们把价格想象成一条数轴，那么物品就是1，小朋友就是-1，价格或者钱就是坐标轴的位置，这道题就转化成了求最大的后缀和大于等于1的下标。

　　最后，我们用线段树来维护这个值，注意用线段树维护最大后缀和时，在查询时要注意后面的区间的影响。

（cin cout清空缓存貌似对于codeforce的多组输出会有影响，去掉了cin，cout的加速就过了，不然一直wa3）

　　　　　　　　　　

 

 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string.h>
using namespace std;
#define ll long longconst int maxn = 1e6 + 10;
const int INF = 0x3f3f3f3f;int n,m;
int a[maxn],b[maxn];
int sum[maxn << 2],maxx[maxn << 2];void update(int o,int l,int r,int ind,int ans)
{if(l == r){sum[o] += ans;maxx[o] += ans;return ;}int mid = (l + r) >> 1;if(ind <= mid)update(o << 1,l,mid,ind,ans);elseupdate(o << 1 | 1,mid + 1,r,ind,ans);sum[o] = sum[o << 1] + sum[o << 1 | 1];maxx[o] = max(maxx[o << 1 | 1],maxx[o << 1] + sum[o << 1 | 1]);
}struct node
{int max,sum;
};
int query(int o,int l,int r,node temp)
{if(l == r)return l;int mid = (l + r) >> 1;node t;t.sum = temp.sum + sum[o << 1 | 1];t.max = temp.sum + maxx[o << 1 | 1];if(t.max > 0)return query(o << 1 | 1,mid + 1,r,temp);elsereturn query(o << 1,l,mid,t);
}
int main()
{//ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);memset(sum,0,sizeof(sum));memset(maxx,0,sizeof(maxx));cin >> n >> m;for(int i = 1; i <= n; i++){cin >> a[i];update(1,1,maxn-1,a[i],1);}for(int i = 1; i <= m; i++){cin >> b[i];update(1,1,maxn-1,b[i],-1);}int q;cin >> q;while(q--){int op,pos,val;cin >> op >> pos >> val;if(op == 1)         //物
        {update(1,1,maxn-1,a[pos],-1);update(1,1,maxn-1,a[pos] = val,1);}else{update(1,1,maxn-1,b[pos],1);update(1,1,maxn-1,b[pos] = val,-1);}if(maxx[1] <= 0)puts("-1");elsecout << query(1,1,maxn-1,{0,0})<<endl;}
}

View Code

 

 

转载于:.html