订正完了就发一下题解吧
第一次写比赛题解
当时我在比赛时A掉了ABCD,E没敢写链表就GG了
所以我订正完后来发一下
A.Beru-taxi
模拟即可
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int a,b,n,pos;
double t=21000000000000000.0;
double Dist(int x,int y,int z){return sqrt(1.0*(x-a)*(x-a)+(y-b)*(y-b))/(1.0*z);}
int main(){
freopen("A.in","r",stdin);
freopen("A.out","w",stdout);
scanf("%d %d",&a,&b);
scanf("%d",&n);
for(int i=1;i<=n;i++){
int tx,ty,s;
scanf("%d %d %d",&tx,&ty,&s);
t=min(Dist(tx,ty,s),t);
}
printf("%.6lf\n",t);
return 0;
}
B.Interesting drink
虽然有线性做法但是二分显然更好写吧……那就写二分
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int n,a[N],m;
int main(){
freopen("B.in","r",stdin);
freopen("B.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
scanf("%d",&m);
while(m--){
int x;
scanf("%d",&x);
printf("%d\n",upper_bound(a+1,a+n+1,x)-a-1);
}
return 0;
}
C.Hard problem
这不是暴力比较就好了?然后做一个贪心(请无视我的数组名)
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100005;
int n,pos[N];
long long dp[N][2],c[N];
char str[N];
bool Big_Small(int x,int inv1,int y,int inv2){
if(!inv1 && !inv2){
int px=pos[y];
for(int i=pos[x];i<pos[x+1];i++,px++){
if(px>=pos[y+1])return 0;
if(str[i]<str[px])return 1;
else if(str[i]>str[px])return 0;
}
return 1;
}
if(inv1 && !inv2){
int px=pos[y];
for(int i=pos[x+1]-1;i>=pos[x];i--,px++){
if(px>=pos[y+1])return 0;
if(str[i]<str[px])return 1;
else if(str[i]>str[px])return 0;
}
return 1;
}
if(!inv1 && inv2){
int px=pos[y+1]-1;
for(int i=pos[x];i<pos[x+1];i++,px--){
if(px<pos[y])return 0;
if(str[i]<str[px])return 1;
else if(str[i]>str[px])return 0;
}
return 1;
}
if(inv1 && inv2){
int px=pos[y+1]-1;
for(int i=pos[x+1]-1;i>=pos[x];i--,px--){
if(px<pos[y])return 0;
if(str[i]<str[px])return 1;
else if(str[i]>str[px])return 0;
}
return 1;
}
}
int main(){
freopen("C.in","r",stdin);
freopen("C.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%I64d",&c[i]);
pos[1]=1;
memset(dp,127,sizeof(dp));
for(int i=1;i<=n;i++){
scanf("%s",str+pos[i]);
pos[i+1]=strlen(str+1)+1;
}
dp[1][0]=0;dp[1][1]=c[1];
for(int i=2;i<=n;i++){
if(Big_Small(i-1,0,i,0))dp[i][0]=min(dp[i-1][0],dp[i][0]);
if(Big_Small(i-1,0,i,1))dp[i][1]=min(dp[i-1][0]+c[i],dp[i][1]);
if(Big_Small(i-1,1,i,0))dp[i][0]=min(dp[i-1][1],dp[i][0]);
if(Big_Small(i-1,1,i,1))dp[i][1]=min(dp[i-1][1]+c[i],dp[i][1]);
}
long long px=min(dp[n][0],dp[n][1]);
printf("%I64d\n",px>=21000000000000000ll?-1ll:px);
return 0;
}
D.Vasiliy's Multiset
字典树裸题……没有任何难度
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200005;
int n,x,st[32],cnt=1;
char str[10];
struct Trie{
int ch[2],num;
}tree[7000005];
void Num(int x){
for(int i=31;i>=0;i--)st[i+1]=(x&(1<<i))>=1;
}
void Add(){
int rt=1;
for(int i=32;i;i--){
if(!tree[rt].ch[st[i]])tree[rt].ch[st[i]]=++cnt;
tree[tree[rt].ch[st[i]]].num++;
rt=tree[rt].ch[st[i]];
}
}
void Del(){
int rt=1;
for(int i=32;i;i--){
if(!tree[rt].ch[st[i]])tree[rt].ch[st[i]]=++cnt;
tree[tree[rt].ch[st[i]]].num--;
rt=tree[rt].ch[st[i]];
}
}
int Ask(){
int rt=1;
for(int i=32;i;i--){
if(tree[tree[rt].ch[!st[i]]].num){rt=tree[rt].ch[!st[i]];st[i]=1;}
else if(tree[tree[rt].ch[st[i]]].num){rt=tree[rt].ch[st[i]];st[i]=0;}
else {break;}
}
int x=0;
for(int i=1;i<=32;i++){x|=(st[i]<<(i-1));/*printf("%d\n",x);*/}
return x;
}
int main(){
freopen("D.in","r",stdin);
freopen("D.out","w",stdout);
scanf("%d",&n);
Add();
while(n--){
int x;
scanf("%s %d",str,&x);
Num(x);
//for(int i=32;i;i--)printf("%d ",st[i]);
//putchar('\n');
if(str[0]=='+')Add();
if(str[0]=='-')Del();
if(str[0]=='?')printf("%d\n",Ask());
}
return 0;
}
E.Working routine
使用十字链表维护整个矩阵，每次修改只改边缘的就好了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1005;
int n,m,mat[N][N],q;
struct Value{
Value *up,*down,*left,*right;
int v;
Value(int x){up=down=left=right=NULL;v=x;}
}*root[N],*Upx[N],*Upy[N],*Downx[N],*Downy[N],*Leftx[N],*Lefty[N],*Rightx[N],*Righty[N];
inline void Initialize(){
for(int i=1;i<=n;i++){
Value *tp;
for(int j=1;j<=m;j++){
if(j==1){
root[i]=new Value(mat[i][j]);
tp=root[i];
}
else {
tp->right=new Value(mat[i][j]);
tp->right->left=tp;
tp=tp->right;
}
}
}
}
inline void Build(){
Value *tp[N];
tp[0]=tp[n+1]=NULL;
for(int i=1;i<=n;i++)tp[i]=root[i];
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){tp[j]->up=tp[j-1];tp[j]->down=tp[j+1];}
for(int j=1;j<=n;j++)tp[j]=tp[j]->right;
}
}
inline void SelectX(Value *r[N],int x,int y,int len){
Value *tp=root[x];
for(int i=1;i<y;i++)tp=tp->right;
for(int i=1;i<=len;i++){r[i]=tp;tp=tp->right;}
}
inline void SelectY(Value *r[N],int x,int y,int len){
Value *tp=root[x];
for(int i=1;i<y;i++)tp=tp->right;
for(int i=1;i<=len;i++){r[i]=tp;tp=tp->down;}
}
inline void PrintMatrix(){
for(int i=1;i<=n;i++){
Value *cur;
for(int j=1;j<=m;j++){
if(j==1)cur=root[i];
else cur=cur->right;
printf("%d ",cur->v);
}
putchar('\n');
}
}
inline void Change(int l1,int r1,int l2,int r2,int h,int w){
Value *tp;
SelectX(Upx,l1,r1,w);
SelectX(Upy,l2,r2,w);
SelectX(Downx,l1+h-1,r1,w);
SelectX(Downy,l2+h-1,r2,w);
SelectY(Leftx,l1,r1,h);
SelectY(Lefty,l2,r2,h);
SelectY(Rightx,l1,r1+w-1,h);
SelectY(Righty,l2,r2+w-1,h);
//for(int i=1;i<=h;i++)printf("%d ",Leftx[i]->v);
//for(int i=1;i<=h;i++)printf("%d ",Lefty[i]->v);
//for(int i=1;i<=h;i++)printf("%d ",Rightx[i]->v);
//for(int i=1;i<=h;i++)printf("%d ",Righty[i]->v);
//for(int i=1;i<=h;i++)printf("%d ",Upx[i]->v);
//for(int i=1;i<=h;i++)printf("%d ",Upy[i]->v);
//for(int i=1;i<=h;i++)printf("%d ",Downx[i]->v);
//for(int i=1;i<=h;i++)printf("%d ",Downy[i]->v);
//putchar('\n');
for(int i=1;i<=h;i++){
if(Leftx[i]->left && Lefty[i]->left){Leftx[i]->left->right=Lefty[i];Lefty[i]->left->right=Leftx[i];tp=Leftx[i]->left;Leftx[i]->left=Lefty[i]->left;Lefty[i]->left=tp;}
else if(Leftx[i]->left && !Lefty[i]->left){Lefty[i]->left=Leftx[i]->left;Leftx[i]->left->right=Lefty[i];Leftx[i]->left=NULL;root[l2+i-1]=Leftx[i];}
else if(!Leftx[i]->left && Lefty[i]->left){Leftx[i]->left=Lefty[i]->left;Lefty[i]->left->right=Leftx[i];Lefty[i]->left=NULL;root[l1+i-1]=Lefty[i];}
else if(!Leftx[i]->left && !Lefty[i]->left){root[l1+i-1]=Lefty[i];root[l2+i-1]=Leftx[i];}
if(Rightx[i]->right && Righty[i]->right){Rightx[i]->right->left=Righty[i];Righty[i]->right->left=Rightx[i];tp=Rightx[i]->right;Rightx[i]->right=Righty[i]->right;Righty[i]->right=tp;}
else if(Rightx[i]->right && !Righty[i]->right){Righty[i]->right=Rightx[i]->right;Rightx[i]->right->left=Righty[i];Rightx[i]->right=NULL;}
else if(!Rightx[i]->right && Righty[i]->right){Rightx[i]->right=Righty[i]->right;Righty[i]->right->left=Rightx[i];Righty[i]->right=NULL;}
}
for(int i=1;i<=w;i++){
if(Upx[i]->up && Upy[i]->up){Upx[i]->up->down=Upy[i];Upy[i]->up->down=Upx[i];tp=Upx[i]->up;Upx[i]->up=Upy[i]->up;Upy[i]->up=tp;}
else if(Upx[i]->up && !Upy[i]->up){Upx[i]->up->down=Upy[i];Upy[i]->up=Upx[i]->up;Upx[i]->up=NULL;}
else if(!Upx[i]->up && Upy[i]->up){Upx[i]->up=Upy[i]->up;Upy[i]->up->down=Upx[i];Upy[i]->up=NULL;}
if(Downx[i]->down && Downy[i]->down){Downx[i]->down->up=Downy[i];Downy[i]->down->up=Downx[i];tp=Downx[i]->down;Downx[i]->down=Downy[i]->down;Downy[i]->down=tp;}
else if(Downx[i]->down && !Downy[i]->down){Downy[i]->down=Downx[i]->down;Downx[i]->down->up=Downy[i];Downx[i]->down=NULL;}
else if(!Downx[i]->down && Downy[i]->down){Downx[i]->down=Downy[i]->down;Downy[i]->down->up=Downx[i];Downy[i]->down=NULL;}
}
}
int main(){
freopen("E.in","r",stdin);
freopen("E.out","w",stdout);
scanf("%d %d %d",&n,&m,&q);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&mat[i][j]);
Initialize();
Build();
while(q--){
int l1,r1,l2,r2,h,w;
scanf("%d %d %d %d %d %d",&l1,&r1,&l2,&r2,&h,&w);
Change(l1,r1,l2,r2,h,w);
}
PrintMatrix();
return 0;
}
这次Div2真是水的可怕……
