然后又退网了

关于

xushuoxin

今 天 心 血 来 潮

破 译 我 的 密 码

帮 我 报 了 比 赛

使 我 猝 不 及 防

水 了 几 个 代 码

ra ting 疯涨 -112

的

这

件

逝

嗨

害

嗨

你知道吗，研表究明，人看在字时，会动自字将排好。

不信你读重一下段这话，会就现发字全是都乱的

#include<bits/stdc++.h>
using namespace std;
int n,Road[1001][1001];
char a[1001][1001];
queue<pair<int,int>> q;
bool ok(int x,int y){
    if(x<0 || x>(n-1) || y<0 || y>(n-1) || a[x][y]=='1') return 0;
    return 1;
}
int main(){
    cin>>n;
    memset(Road,-1,sizeof(Road));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    }
    int start_x,start_y;
    int end_x,end_y;
    cin>>start_x>>start_y>>end_x>>end_y;
    start_x--;
    start_y--;
    end_x--;
    end_y--;
    q.push(make_pair(start_x,start_y));
    Road[start_x][start_y]=0;
    int move_x[4]={0,1,-1,0};
    int move_y[4]={1,0,0,-1};
    pair<int,int> p;
    while(!q.empty()){
        p=q.front();
        q.pop();
        int x=p.first;
        int y=p.second;
        int nx,ny;
        for(int i=0;i<4;i++){
            nx=x+move_x[i];
            ny=y+move_y[i];
            if(ok(nx,ny)==1 && Road[nx][ny]==-1){
                q.push(make_pair(nx,ny));
                Road[nx][ny]=Road[x][y]+1;
            }
        }
    }
    cout<<Road[end_x][end_y];
    return 0;
}

0分，输出都是-1，但本地自测样例没问题

昨天月赛的E题我写的程序本是60分的

但现场只得了40分

刚才才发现是把D题的程序交了上去

所以输出全是0

这么说，我如果提交对了，总分应是414分

可以得到第7名

而事实只有第10名

本来能加点rating

现在却扣了一堆

------------------------------------------------------------------

长教训了！

就算比赛只剩一秒钟也不能急

着急了很容易出事

希望大家引以为戒

避免这种情况再次发生

------------------------------------------------------------------

题外话：E题数据竟然有4个都输出0，要不然我会爆0，那rating可不扣到1500以下了！（太侥幸了！）

#12865. 找朋友(friend)

70分做法：不少人都得了70分，思路很简单，分两种情况讨论

1.编号小的到编号大的
2.编号大的到编号小的（因为小朋友们围成了一个圈）

70分代码：

#include<bits/stdc++.h>
using namespace std;    
int n,a[10005],sum=0;
void solve(){
    int xx,yy;
    cin>>xx>>yy;
    int x=min(xx,yy),y=max(xx,yy);
    int sum1=0,sum2=0;
    for(int i=x;i<y;i++){
        sum1+=a[i];
    }
    sum2=sum-sum1;
    sum1*=(y-x);
    x+=n;
    sum2*=(x-y);
    cout<<min(sum1,sum2)<<endl;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    int k;
    cin>>k;
    while(k--){
        solve();
    }
    return 0;
}

但令人悲伤的是：

对于 100% 的数据， 满足 n<=10000, k<=1000000

而上面的做法复杂度为O(nk),妥妥的TLE！

所以我们需要对此进行优化

其中有k组数据所以要循环k次，这是不可以省略的

所以我们只能优化O（n）的循环

-------------------------------------------------分界线-------------------------------------------------------

此处强烈建议食用前缀和

先跳脱出小朋友围成一圈的情境

举个栗子：

编号  1  2  3  4  5

数值  10 20 30 40 50

题目中我们要求的是从一个编号到另一个编号数值之和

比如：

求编号3-5的数值之和

刚才我们用了循环累加法

需要耗费O（n）的复杂度

但是我们可以先将1-5的数值和算出来

再减去1-2的数值和

就能快速得出3-5的数值和了

不信？验算一下：

1-5：10+20+30+40+50=150

1-2：10+20=30

3-5：30+40+50=120

而150-30=120

所以可以得出规律：

x-y的数值和=1-y之和减去1-（x-1）的和

这样只需要在输入时每次统计一边=遍前缀和（即这个位置到第一个位置的权值和）

每次计算使用即可，一劳永逸！

注意点：

1.输入的x和y不一定有序，需要手动确保有序

2.开long long + printf + scanf

3.x,y在计算前都要-1

AC主代码：

long long sum1=(dis[y]-dis[x])*(y-x);
long long sum2=(dis[n]-dis[y]+dis[x])*(x+n-y);

@zuotingting

请问#12865. 找朋友(friend)的正解是什么？（我想方设法也只得了70分，最后三个点TLE）。

把#1015的程序交到#4612里

没准有惊喜！

    n=input(int())
    ans=int()
    ans=1
    for i in range(n):
        ans*=2
    ans=ans-1
    ans=ans*2
    print(ans)

我的每个输出都有前导0

请问怎么去掉前导0？

（本人对Python基本一窍不通，这是小学信息课学的）

强列西忘