2020.2.6試合の問題解

T 1文字列脱重
この問題は言うまでもなく、どうでもいい.
本題の文字列はすでに順番に並んでいるので、この文字列と前の文字列が等しいかどうかを直接判断すればいい.
全部読み込んでC++が持つ(unique)関数でやり直すこともできます.
複雑度(O(Sigma len)).
スレッド:

#include
using namespace std;
string s[100010];
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) cin>>s[i];
    n=unique(s+1,s+n+1)-s-1;
    for(int i=1;i<=n;i++) cout<

T 2クロススター
この問題は難しくありません.私はまた一定の難易度を下げて、カードの精度がなくて、カードの常です.
この問題は2種類に分けて考慮して、傾きの積は-1に等しくて、あるいは平行と座標軸で、みんながどのように2点の直線の傾きを求めることを知っていると信じています.(i)番目の点の座標を((x_i,y_i))とすると、(i,j)番目の点を通過する直線の傾きが(frac{y_i-y_j}{x_i-x_i-x_j})となり、(y_i-y_j=0)の場合、その直線は(x)軸に平行であり、(x_i-x_j=0)の場合、その直線は(y)軸に平行である.
(500)個を超えない点しかないので、(frac{500times(500-1)}{2}=124750)を超えない直線しかありません.暴力が維持される場合、時間の複雑さは(O(n^4))である.
傾きを1つのデータ構造で維持することを考慮すると、(STL)のマッピングコンテナ(map)を使用して維持することは容易である.線分を1つ加えるたびに、増加した答えを統計します.
複雑度(O(Tn^2 log(n))
スレッド(1):

#include
using namespace std;
struct node{int x,y;}p[510];
map mp; 
int T,n;
int main(){
    scanf("%d",&T);
    while(T--){
    mp.clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d %d",&p[i].x,&p[i].y);
        int cnt1=0,cnt2=0;
        long long ans=0;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(p[i].x==p[j].x) cnt1++;
                else if(p[i].y==p[j].y) cnt2++;
                else{
                    double x=(p[i].x-p[j].x),y=(p[i].y-p[j].y);         
                    mp[x/y]++;
                    ans+=mp[-y/x];
                }
            }
        }
        printf("%lld
",ans*4+(long long)cnt1*cnt2*4);
    }
}

スレッド(2):

#include
using namespace std;
struct node{int x,y;}p[510];
map,int> mp; 
int T,n;
int gcd(int x,int y){
    if(x%y==0) return y;
    return gcd(y,x%y);
}
int main(){
    scanf("%d",&T);
    while(T--){
    mp.clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d %d",&p[i].x,&p[i].y);
        int cnt1=0,cnt2=0;
        long long ans=0;
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                if(p[i].x==p[j].x) cnt1++;
                else if(p[i].y==p[j].y) cnt2++;
                else{
                    int x=(p[i].x-p[j].x),y=(p[i].y-p[j].y),gc=abs(gcd(x,y));
            x/=gc;y/=gc;
            if(x<0) x*=-1,y*=-1;                    
                    mp[make_pair(x,y)]++;
                    if(y<0) x*=-1,y*=-1;
                    ans+=mp[make_pair(y,-x)];
        }
        }
    }
    printf("%lld
",ans*4+(long long)cnt1*cnt2*4);
    }
}

T 3迷宮の道を探す
この問題は主にみんなの広捜に対する理解を考察した.
前の(40)点に対して、直接深く探せばいい、(O(玄学)).
中間の(30)点については,広捜の古典的な例題であり,直接広捜,(O(nm))であることが容易にわかる.
すべてのデータについて、広捜を改良しようと試みた.広捜の思想は1つの優先キューを維持して、今距離の小さい位置を前に置いて、距離の大きい位置を後ろに置いて、本題の中でチームの頭とチームの尾の値の差は1を超えません.
現在、キューを取り出し、キューの距離を(dis)とし、トランスポートゲートを使用し、((i,j))位置に到達したと考えると、((i,j))の距離を(dis)に更新し、元のキューが最小であるため、直接キューに入れればよい.
さらに隣接する格子((i,j))まで歩くことを考慮して、距離は(dis+1)で、チームヘッドとチームテールの差は(1)より大きくないので、チームテールに入れればよい.
全複雑度(O(nm)).
スレッド:

#include
using namespace std;
int n,m,k,dis[2010][2010],vis[2010][2010],nxt[5][2]={{},{0,1},{0,-1},{1,0},{-1,0}};
char ch[2010][2010];
pair q[5000010];
vector > v[2010][2010];
int main(){
    for(int i=0;i<=2005;i++){
        for(int j=0;j<=2005;j++) ch[i][j]='#',dis[i][j]=2e9;
    }
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) scanf(" %c",&ch[i][j]);
    }
    scanf("%d",&k);
    int x0,y0,x1,y1;
    while(k--){
        scanf("%d %d %d %d",&x0,&y0,&x1,&y1);
        v[x0][y0].push_back(make_pair(x1,y1));
    }
    int l=1000000,r=1000000;
    q[1000000]=make_pair(1,1);
    dis[1][1]=0;
    while(l<=r){
        int x=q[l].first,y=q[l].second;
        l++;
        if(vis[x][y]) continue;
        vis[x][y]=1;
        for(int i=0;i

T 4家計簿の整理
この問題はビット演算に関する分析を少し受けた.
(i&(i-1))が何を表しているのか考えてみましょう.(10)を例にしてみましょう.(10&9=8)つまり((1010)2\&(1001)_2=(1000)_2)、つまりバイナリの下の最下位を外したことに相当します.
現在は(i)の最後の位置を考え、現在は右から左へ数える(k)位を考えると、彼の父は(i-2^{k-1})である.私たちは(2^{k-1}|i)を知ることができて、しかも(2^kmid i)なので、せっかく(2^k|i-2^k)を得ることができなくて、それから(i-2^kin[l,r])を知っているので、直接除算で([l,r])の中の(2^k)の倍数を統計すればいいので、境界が取れるかどうかを分類して考えてください.
複雑度(O(Tlog(値域)approx O(50 T)).
スレッド:

#include
using namespace std;
int n;
long long l,r;
int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%lld %lld",&l,&r);
        long long ans=0;
        for(int i=60;i>=1;i--){
            long long nl=floor((double)(l-1)/(1LL<nr) continue;
            if((nr<r) ans+=nr-nl;
            else ans+=nr-nl+1;
        }
        printf("%lld
",ans);
    }
}

完結散花QQQ