Codeforces Round #182 (Div. 1)题解
A题:Yaroslav and Sequence1
题意:
给你\(2*n+1\)个元素,你每次可以进行无数种操作,每次操作必须选择其中n个元素改变符号,你的目的是使得最后所有数的和尽量大,问你答案是多少
题解:
感觉上就是构造题,手动玩一玩就知道,当n为奇数的时候,你可以通过三次操作,使得只会改变一个负数的符号。同理n为偶数的时候,每次要改变两个负数的符号。
所以答案如下:
当n为奇数的时候,答案为所有数的绝对值和
当n为偶数的时候,负数个数为偶数的时候,答案为所有数的绝对值和,否则就让绝对值最小的那个数取负数就好了。
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
int a[maxn],n,sum,tmp=1001,fu;
int main()
{
scanf("%d",&n);
for(int i=0;i<2*n-1;i++){
scanf("%d",&a[i]);
sum+=abs(a[i]);
if(a[i]<0)
fu++;
tmp=min(tmp,abs(a[i]));
}
if(n%2==1){
cout<<sum<<endl;
}else{
if(fu%2==1){
cout<<sum-2*tmp<<endl;
}else{
cout<<sum<<endl;
}
}
}
B题:Yaroslav and Time1
题意:
给你一个二维平面,你要从1走到n去,两点之间的距离等于abs(x[i]-x[j])+abs(y[i]-y[j]),然后你到达j点的时候,可以让时间提前a[i],问你最快到达n点是什么时候。
题解:
明显的傻逼题嘛,floyd一下就好了
代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 106;
int n,d,a[maxn],mp[maxn][maxn],x[maxn],y[maxn];
int main()
{
scanf("%d%d",&n,&d);
for(int i=2;i<=n-1;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
scanf("%d%d",&x[i],&y[i]);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)continue;
mp[i][j]=(abs(x[i]-x[j])+abs(y[i]-y[j]))*d-a[j];
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
}
}
}
cout<<mp[1][n]<<endl;
}
C题:Yaroslav and Algorithm
题意:
让你写一个程序,只能包含数字和问号,以及一个>>符号,或者<>符号。使得数通过这个算法之后,增加1.
具体语法如下:
1.首先读入一个字符串s
2.你的程序包括若干行代码,形式为si>>wi,或者si<>wi,si和wi只能由数字或者问号组成
3.在程序中找到最小的i,使得si是s的子串,然后将第一个出现的si替换成为wi,如果符号为>>的话,重新执行这一步,如果为<>的话,终止程序
4.如果找不到i,那么终止程序。
题解:
加一,其实只用考虑最后一位是什么就好了。
所以先找到最后一位是什么,这个是最关键的。
我们先把问号扔到前面,然后再把问号不断往后传就好了。
代码
#include<stdio.h>
int main()
{
int i;
for (i=0; i<9; i++) printf("%d\?\?<>%d\n",i,i+1);
puts("9\?\?>>\?\?0\n\?\?0<>10");
for (i=0; i<=9; i++) printf("\?%d>>%d\?\n",i,i);
puts("\?>>\?\?\n>>\?");
}
D题:Yaroslav and Divisors
题意:
给你n个数的1-n的排列,Q次询问,每次询问一个区间里面有多少对数满足a[i]%a[j]=0(l<=i,j<=r)
题解:
离线处理,按照L坐标大的排前面排序,预处理E[i][j]表示 a[j] mod a[i] == 0,L倒着枚举,然后
然后不断更新这个值,update(j,1),然后每次答案就是ask(r)。因为r一定是小于等于r的数更新过来的,且现在只更新到L,所以ask(r)就等与[L,r]的值
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+7;
vector<int>E[maxn];
struct node{
int l,r,id;
}Q[maxn];
bool cmp(node A,node B){
return A.l>B.l;
}
int n,m,ans[maxn],pos[maxn],d[maxn],a[maxn];
int lowbit(int x){
return x&(-x);
}
void add(int x){
for(int i=x;i<maxn;i+=lowbit(i))
d[i]++;
}
int ask(int x){
int res = 0;
for(int i=x;i;i-=lowbit(i))
res+=d[i];
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),pos[a[i]]=i;
for(int i=1;i<=m;i++){
scanf("%d%d",&Q[i].l,&Q[i].r);
Q[i].id=i;
}
sort(Q+1,Q+1+m,cmp);
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j+=i){
E[min(pos[i],pos[j])].push_back(max(pos[i],pos[j]));
}
}
int L=n;
for(int i=1;i<=m;i++){
while(L>=Q[i].l){
for(int j=0;j<E[L].size();j++)
add(E[L][j]);
L--;
}
ans[Q[i].id]=ask(Q[i].r);;
}
for(int i=1;i<=m;i++)
cout<<ans[i]<<endl;
}