比赛地址
Pro: 8/8/12
Rank: 71/1175
[A] Clam and Fish
题意
有一片池塘,有四个状态,有/无蛤蜊,有/无鱼.有蛤蜊的时候可以做一个诱饵,有鱼的时候可以直接钓鱼.其他时间可以消耗一个诱饵钓一条鱼.求最多能钓几条鱼.
题解
贪心.在有鱼的时候尽量钓,其他时间做诱饵.
如果最后会剩下诱饵就在做后面一半诱饵的时候钓鱼.
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int n, a[2000005], T, tot, ans, now;
char s[2000005];
int main() {
scanf("%d", &T); while(T--) {
scanf("%d%s", &n, s);
tot = ans = now = 0;
for (int i = 0; i < n; i++) if (s[i]=='0'||s[i]=='1') a[++tot] = s[i]-'0';
for (int i = 1; i <= tot; i++) {
if (now >= (tot-i+1)) {
now--;
ans++;
} else if (now && a[i]==0) {
now--;
ans++;
} else if (a[i]==1) {
now++;
}
}
printf("%d\n", ans+n-tot);
}
return 0;
}
[B] Classical String Problem
题意
给出一个字符串,有两种操作,一种是把最前面的k个字符挪到最后面,另一种是把最后面的k个字符挪到最前面.还有一些询问操作,每次问某个位置的字符是什么.
题解
首尾相接拼成一个环,然后更新首字符所在的位置就行了.
一开始失了智写了个Splay维护区间,还T了一发QAQ
代码
#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) s[x][0]
#define r(x) s[x][1]
#define IL inline
#define reg register
#define LL long long
#define N 4000010
#define INF 0x3f3f3f3f
using namespace std;
int n,m,i,x,root,len;
char op;
char c[N];
int tag[N],f[N],s[N][2],size[N],id[N];
IL bool Get(int x){return (x==s[f[x]][1]);}
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
IL void Query(){
int y=0;
y=(root+x-1)%len;
if (y==0) y=len;
printf("%c\n",c[y]);
}
IL void Work(){
int l=0,r=0,t=0,u=0;
root+=x;
root=root%len;
if (root==0) root=len;
while (root<0) root+=len;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%s",c+1);
for (len=1;c[len]!='\0';len++);
len--;
n=read(); root=1;
for (i=1;i<=n;i++){
scanf("%c%d",&op,&x); getchar();
(op=='A')?Query():Work();
}
return 0;
}
[C] Operation Love
## 题意
给出一个右手的形状,左手与右手是镜像对称的.现在给出一个图形,判断是左手还是右手.
题解
机器学习
可以找一些特殊的向量来判断叉积,卡精度.
代码
#include <cstdio>
#include <cmath>
using D = double;
constexpr int N(20);
constexpr int sign(D x, D eps)
{
return x<-eps ? -1 : (x>eps ? 1 : 0);
}
constexpr D dis2(D x1, D y1, D x2, D y2)
{
return (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
}
int main()
{
D x[123], y[213];
int t;
scanf("%d", &t);
while (t--)
{
double xx, yy;
for (int i=0; i<N; ++i)
scanf("%lf %lf", &xx, &yy), x[i] = xx, y[i] = yy;
for (int i=1; i<N; ++i)
x[i]-=x[0], y[i]-=y[0];
x[0] = y[0] = 0;
auto prev = [&](int x){return x>0 ? x-1 : N-1;};
auto next = [&](int x){return x<N-1 ? x+1 : 0;};
for (int i=0; i<N; ++i)
{
int j = next(i);
if (!sign(dis2(x[i], y[i], x[j], y[j])-D(64), 3))
{
int k10_0, k10_8, k1_0;
int jj = next(j);
if (!sign(dis2(x[j], y[j], x[jj], y[jj])-D(81), 3))
k10_0 = j, k10_8 = i, k1_0 = jj;
else
k10_0 = i, k10_8 = j, k1_0 = prev(i);
D xa = x[k10_8]-x[k10_0], ya = y[k10_8]-y[k10_0];
D xb = x[k1_0]-x[k10_0], yb = y[k1_0]-y[k10_0];
int s = sign(xa*yb - ya*xb, 3);
if (s > 0)
puts("right");
else
puts("left");
break;
}
}
}
return 0;
}
[D] Points Construction Problem
题意
给出一个无限大的网格平面,一开始每一个格子都是白色的.现在要求将n个格子染成黑色,使得相邻的两个格子为黑白两色的格子对的数目恰好为m.求染色方案.
题解
m为奇数一定无解,且m最大为4n.然后当这些黑色格子构成一个正方形时,黑白格子对数目最少.
根据以上信息简单构造下就行了.
代码
#include <cstdio>
#include <cmath>
#include <iostream>
int n, m, T;
int s[55][55], x[55], y[55], cnt, tot;
int main() {
scanf("%d", &T); for (int t = 1; t <= T; t++) {
scanf("%d%d", &n, &m);
int k; for (k = 1; k*k<=n; k++);
k--;
int mi = 0;
cnt = 0; tot = 0;
for (int i = 1; i <= 50; i++) for (int j = 1; j <= 50; j++) s[i][j] = 0;
for (int i = 1; i <= 50; i++) x[i] = y[i] = 0;
for (int i = 1; i <= 50; i++) if(tot!=n) for (int j = 1; j <= k; j++) {
s[i][j] = 1;
if (i != 1 && j != 1) {
cnt++;
x[cnt] = i; y[cnt] = j;
}
mi = i;
tot++;
if (tot == n) break;
}
int now = (mi+k)*2;
if (m%2 || m<now || m > n*4) {
printf("No\n");
continue;
} printf("Yes\n");
int need = (m-now)/2;
int nowy = k+1;
while(need&&cnt) {
s[1][nowy++] = 1;
s[x[cnt]][y[cnt]] = 0;
cnt--;
need--;
}
if (need == 0) {
for (int i = 1; i <= 50; i++) for (int j = 1; j <= 50; j++)
if (s[i][j] == 1) printf("%d %d\n", i, j);
continue;
}
for (int i = 50; i >= 1; i--) for (int j = 1; j <= 50; j++)
if (s[i][j] == 1) {
cnt++;
x[cnt] = i; y[cnt] = j;
}
while(need&&cnt) {
s[x[cnt]][y[cnt]] = 0;
s[50-cnt%2][cnt] = 1;
cnt--;
need--;
}
for (int i = 1; i <= 50; i++) for (int j = 1; j <= 50; j++)
if (s[i][j]) printf("%d %d\n", i, j);
}
return 0;
}
[E] Two Matchings
题意
给一个长度为n的序列,定义重排方案p为,p_{i}!=i,p_{p_{i}}=i.且p为1到n的一个排列.
现在要求找出两个完全不同的重排方案p,q(也就是两个排列对应位置均不相同),使得原序列在分别经过这两个重排后的代价之和最小.求这个最小代价.
代价的定义是\sum_{i=1}^{n}\frac{a_{i}-a_{i}'}{2}
题解
不难发现,当n=4,6时,答案就是最大值减去最小值的两倍.当n比较大时,就需要把这个序列切为一些小段,每一个小段的代价也是最大值减去最小值的两倍.
所以有如下dp式子:f[i]=Min(f[i],f[j]+2(a[i]-a[j+1]).其中的a是从大到小排好序的.这个式子和单调队列优化dp的式子非常像,不过这里只需要记录下f[i]-2a[i+1]的最大值.之后直接dp就行了.
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<queue>
#define l(x) (x<<1)
#define r(x) ((x<<1)|1)
#define IL inline
#define reg register
#define LL long long
#define N 200010
#define INF 0x3f3f3f3f3f3f3f3fll
using namespace std;
LL T,n,i,x,y,Ans;
LL a[N],f[N];
priority_queue <LL> Q1,Q2;
IL LL Min(LL a,LL b){return (a<b)?a:b;}
IL LL Max(LL a,LL b){return (a>b)?a:b;}
IL LL read(){
LL p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=read();
while (T--){
n=read();
for (i=1;i<=n;i++) a[i]=read();
sort(a+1,a+1+n);
if (n<=6){
printf("%lld\n",2*(a[n]-a[1]));
continue;
}
while (!Q1.empty()) Q1.pop();
while (!Q2.empty()) Q2.pop();
for (i=1;i<=n;i++) f[i]=INF;
f[4]=2*(a[4]-a[1]);
f[6]=2*(a[6]-a[1]);
Q1.push(2*a[5]-f[4]);
for (i=8;i<=n;i+=2){
x=-Q1.top();
if (!Q2.empty()) y=-Q2.top(); else y=INF;
f[i]=Min(f[i],x+2*a[i]);
f[i]=Min(f[i],y+2*a[i]);
if (i%4) Q1.push(2*a[i-1]-f[i-2]);
else Q2.push(2*a[i-1]-f[i-2]);
}
printf("%lld\n",f[n]);
}
return 0;
}
[F] Fraction Construction Problem
题意
给出a,b,求c,d,e,f,使得\frac{c}{d}-\frac{e}{f}=\frac{a}{b}.
且要满足d,f<b
题解
变形,有\frac{cf-ed}{df}=\frac{a}{b}.将b拆分成互质的两个数,作为d和f.此时由裴蜀定理可知,上面这个不定方程是有解的,解出c,e即可.
当b只含有一个质因子或者在b<1时是无解的.还有一些其他特殊的情况也要特判掉.
代码
#include <cstdio>
#include <cmath>
#include <iostream>
int p[2000005];
void Ex_gcd(long long int a, long long int b, long long int &x, long long int &y) {
if (b == 0) { x = 1; y = 0; return; }
long long int x1, y1;
Ex_gcd(b, a%b, x1, y1);
x = y1; y= x1-(a/b)*y1;
}
long long int gcd(long long int a, long long int b) {
if (b==0) return a;
return gcd(b, a%b);
}
long long int a, b, x, y, k1, k2, pb, B;
int main() {
for (int i = 1; i <= 2000000; i++) p[i] = 0;
for (int i = 2; i <= 2000000; i++)
if (p[i] == 0) for (int j = 1; j <= 2000000/i; j++)
if (p[i*j] == 0) p[i*j] = i;
int T; scanf("%d", &T); while (T--) {
scanf("%lld%lld", &a, &b);
if (b >= 2 && a%b==0) {
long long int k = a/b;
printf("%lld %lld %lld %lld\n", k+1, 1, 1, 1);
continue;
}
if (b <= 2) {
printf("-1 -1 -1 -1\n");
continue;
}
long long int k = gcd(a, b);
a /= k; b /= k;
x, y, k1 = 1, k2, pb = p[b], B = b;
while(B%pb==0) {
k1 *= pb;
B /= pb;
}
k2 = B;
if (k == 1 && k2 == 1) {
printf("-1 -1 -1 -1\n");
continue;
}
Ex_gcd(k1, k2, x, y);
if (x > k2) {
long long int k = x/k2;
x -= k*k2;
y += k*k1;
}
if (y > k1) {
long long int k = y/k1;
y -= k*k1;
x += k*k2;
}
if (x < 0) {
x = -x;
if (x == 0 || y == 0) { x+=k2; y+=k1; }
printf("%lld %lld %lld %lld\n", y*a, k1, x*a, k2);
}
else {
y = -y;
if (x == 0 || y == 0) { x+=k2; y+=k1; }
printf("%lld %lld %lld %lld\n", x*a, k2, y*a, k1);
}
}
return 0;
}
[G] Operating on a Graph
题意
给出一个图,有n个集合.一开始,第i个集合中只有点i.接下来有一系列操作,每次会钦定一个集合x,把与x相邻的所有集合全部并到x集合中.求在这些操作后,每个点分别属于哪些集合.
集合相邻的定义是,存在一条边,连接了两个集合中的一对点.
题解
首先,把集合的合并想象成染色操作,不难发现,每条边至多会传递染色操作一次.于是,对于每一个集合,维护这个集合有哪些边,是连接了这个集合的点与集合外的点.每一次合并的时候,就通过这些边找到相邻的集合来合并,通过并查集维护集合的关系.合并之后,更新一下新集合的边集.
一开始,每一条边一定会属于两个边集,且边集的总大小是不变的,故使用按秩合并的话,时间复杂度就可以降为O(mlogm).边集的储存通过vector实现,内存方面就没问题了.
代码
#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define IL inline
#define reg register
#define N 800010
using namespace std;
int T,n,m,i,k,x;
int f[N],fa[N],v[N];
struct Data{
int x,y;
}a[N];
vector <int> P[N];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
char buf[1<<15],*fs,*ft;
inline char gc(){
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int gint(){
int x=0,ch=gc();
while(ch<'0'||ch>'9') ch=gc();
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=gc();
return x;
} //Fastest Read
int sta[15];
IL void Write(int x){
reg int top=0;
do{
sta[top++]=x%10,x/=10;
}while (x);
while (top) putchar(sta[--top]+48);
putchar(' ');
}
IL int Find(int x){return (x==fa[x])?x:fa[x]=Find(fa[x]);}
IL void Ready(){
reg int i=0;
for (i=1;i<=n;i++) f[i]=i,fa[i]=i;
for (i=1;i<=m;i++){
P[a[i].x].push_back(i); P[a[i].y].push_back(i); v[i]=1;
}
}
IL void Merge(int x){
reg int u=f[x],i=0,p=0,q=0,ff=0;
fa[x]=Find(fa[x]);
if (fa[x]!=x) return;
for (auto j : P[u]){
if (!v[j]) continue;
if (Find(a[j].x)==x && Find(a[j].y)==x) continue;
if (Find(a[j].x)==x){
if (!p){
p=f[Find(a[j].y)];
} else {
q=f[Find(a[j].y)];
if (P[q].size()<P[p].size()){
P[p].insert(P[p].end(),P[q].begin(),P[q].end());
//vector<int> ().swap(P[q]);
//vector <int> (P[q]).swap(P[q]);
P[q].clear();
} else {
P[q].insert(P[q].end(),P[p].begin(),P[p].end());
//vector <int> (P[p]).swap(P[p]);
P[p].clear();
//vector<int> ().swap(P[p]);
p=q;
}
}
ff=Find(a[j].y); fa[ff]=x;
} else {
if (!p){
p=f[Find(a[j].x)];
} else {
q=f[Find(a[j].x)];
if (P[q].size()<P[p].size()){
P[p].insert(P[p].end(),P[q].begin(),P[q].end());
//vector<int> ().swap(P[q]);
//vector <int> (P[q]).swap(P[q]);
P[q].clear();
} else {
P[q].insert(P[q].end(),P[p].begin(),P[p].end());
//vector<int> ().swap(P[p]);
//vector <int> (P[p]).swap(P[p]);
P[p].clear();
p=q;
}
}
ff=Find(a[j].x); fa[ff]=x;
}
}
for (auto j : P[u]) v[j]=0;
if (p)
f[x]=p;
else
P[u].clear();
//vector<int> ().swap(P[u]);
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
T=gint();
while (T--){
n=gint(); m=gint();
for (i=1;i<=m;i++)
a[i].x=gint()+1,a[i].y=gint()+1;
Ready();
k=gint();
while (k--){
x=gint()+1; Merge(x);
}
for (i=1;i<=n;i++) Write(Find(i)-1);
puts("");
for (i=0;i<=n;i++){
//vector<int> ().swap(P[i]);
P[i].clear();
//vector <int> (P[i]).swap(P[i]);
}
}
return 0;
}
[L] Problem L is the Only Lovely Problem
题意&题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define IL inline
#define reg register
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int i,j,flag;
char c[110];
IL int Abs(int x){return (x<0)?-x:x;}
IL void Swap(int &a,int &b){a^=b^=a^=b;}
IL int Min(int a,int b){return (a<b)?a:b;}
IL int Max(int a,int b){return (a>b)?a:b;}
IL int read(){
int p=0,f=1; char c=getchar();
while (c<48||c>57) {if (c=='-') f=-1; c=getchar();}
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p*f;
}
int main(){
#ifdef __Marvolo
freopen("zht.in","r",stdin);
freopen("zht.out","w",stdout);
#endif
scanf("%s",&c);
for (i=0;i<strlen(c);i++) if (c[i]<'a') c[i]=c[i]+'a'-'A';
if (c[0]!='l' || c[1]!='o' || c[2]!='v' || c[3]!='e' || c[4]!='l' || c[5]!='y') puts("ugly");
else puts("lovely");
return 0;
}
总结
整场比赛基本上没有闲着的时候.
签完到之后在想F和G.G题一开始的写法有问题,导致莫名MLE,中间还针对vector换了一个释放内存的写法2333.思路是对的,但是码力没太跟上,浪费了很多时间也多吃了好几次罚时.F题的推导速度也有些慢,直接导致了在最后一小时才发现D题很可做(当然这跟榜有些歪也有关系).五个小时连WA带调就这么过去了.
之后的工作重点还是在尽可能减少罚时上.
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: 2020牛客暑期多校第三场
本文地址: 2020牛客暑期多校第三场
