正睿暑期培訓day1考試

来源:https://www.cnblogs.com/wxyww/archive/2019/08/29/11428258.html
-Advertisement-
Play Games

"鏈接" A 理解一下題意，然後玩幾組樣例就能發現，實際上就是$k$個$i$等價於$1$個$i 1$。所以就類似於$k$進位進行進位，如果最後$0$位上不是$0$，那麼就存在劃分方案。否則就不存在劃分方案。 輸出第一次劃分方案就記錄一下每個數字是不是後面的數字湊出來的。如果是的話就像後面數字連邊。這 ...


鏈接

A

理解一下題意，然後玩幾組樣例就能發現，實際上就是\(k\)個\(i\)等價於\(1\)個\(i-1\)。所以就類似於\(k\)進位進行進位，如果最後\(0\)位上不是\(0\)，那麼就存在劃分方案。否則就不存在劃分方案。

輸出第一次劃分方案就記錄一下每個數字是不是後面的數字湊出來的。如果是的話就像後面數字連邊。這樣就形成了一棵\(k\)叉樹。最後\(dfs\)一遍輸出即可。

考場上\(vector\)下標從1開始記錄了。就\(wa\)慘了。。。

/*
* @Author: wxyww
* @Date: 2019-08-04 11:41:21
* @Last Modified time: 2019-08-04 16:08:45
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 200000 + 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int vis[N],tot;
int n,K;
vector<int>e[N * 10],ans[N];
void print(int pos,int u) {
    if(u <= n) {
        ans[pos].push_back(u);vis[u] = 1;return;
    }
    int k = e[u].size();
    for(int i = 0;i < k;++i) {
        print(pos,e[u][i]);
    }
}
int main() {
    int T = read();
    while(T--) {

         n = read(),K = read();
        tot = n;        
        for(int i = 1;i <= n;++i) e[read()].push_back(i);

        for(int i = n;i > 1;--i) {
            int k = e[i].size();
            while(k >= K) {
                ++tot;
                for(int j = 1;j <= K;++j,k--) {
                    e[tot].push_back(e[i][k - 1]);
                }
                e[i - 1].push_back(tot);
            }
        }
        if(e[1].size() < K) {
            puts("0");
            for(int i = 0;i <= tot;++i) e[i].clear();
            for(int i = 0;i <= K;++i) ans[i].clear();
            memset(vis,0,sizeof(vis)); 
            continue;
        }
        puts("1");


        for(int i = 0;i < K;++i) {
            int k = e[1][i];
            print(i + 1,k);
        }

        for(int i = 1;i <= n;++i) if(!vis[i]) ans[1].push_back(i);
        
        for(int i = 1;i <= K;++i) {
            int k = ans[i].size();
            printf("%d ",k);
            for(int j = 0;j < k;++j) printf("%d ",ans[i][j]);
            puts("");
        }
    
        for(int i = 0;i <= tot;++i) e[i].clear();
        for(int i = 0;i <= K;++i) ans[i].clear();
        memset(vis,0,sizeof(vis)); 

    }

    return 0;
}

B

考場上只會一個暴力並查集的做法。就是每次暴力將相同的位置並起來，最後查詢。然鵝，，，，沒註意到"後面一個區間不能相交"這個重要條件。。。然後就硬生生把複雜度對的42分程式通過數據分治改成了22分的好成績233.。。

只要將並查集改成暴力這題就能A了。。。
對於已經給出的每一位，都根據給出的相等條件不斷向前跳，將這個字元儲存在第一個可知的位置。對於後面的詢問，用同樣的方法向前跳即可。

考慮一下向前跳的複雜度。

enter description here

如圖，我們已知兩個黑色矩形區域是相等的。那麼顯然這兩個區域都含有一個長度為t的迴圈節。我們如果暴力跳的話就要跳\(\frac{len}{t}\)次。所以我們直接計算出最前面那個迴圈節中與當前查詢字元相等的位置，直接跳過去即可。
這樣每個條件都只會最多跳一次。所以複雜度就是\(O(m)\)的。

/*
* @Author: wxyww
* @Date: 2019-08-04 19:52:20
* @Last Modified time: 2019-08-04 20:16:31
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
const int N = 1000100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m1,m2,Q;
struct node {
    int l1,r1,l2,r2;
}a[N];
pair<int,char> b[N];
bool cmp(const node &A,const node &B) {
    return A.l2 < B.l2;
}
map<int,char>ans;

int erfen(int x) {
    int ret = 0,l = 1,r = m2;
    while(l <= r) {
        int mid = (l + r) >> 1;
        if(x <= a[mid].r2) ret = mid,r = mid - 1;
        else l = mid + 1;
    }
    return ret;
}

int find(int x) {

    while(1) {
        int p = erfen(x);
        if(a[p].l2 > x || a[p].r2 < x) return x;
        int tmp = a[p].l2 - a[p].l1;
        x = x - (x - a[p].l2) / tmp * tmp;
        while(x >= a[p].l2) x -= tmp;
    }

}

int main() {
    n = read(),m1 = read(),m2 = read(),Q = read();
    for(int i = 1;i <= m1;++i) {
        int x = read();char c;
        scanf("%c",&c);
        b[i] = make_pair(x,c);
    }

    for(int i = 1;i <= m2;++i) {
        a[i].l1 = read();a[i].r1 = read();a[i].l2 = read();a[i].r2 = read();
    }

    sort(a + 1,a + m2 + 1,cmp);

    for(int i = 1;i <= m1;++i) ans[find(b[i].first)] = b[i].second;


    while(Q--) {
        int x = find(read());
        if(!ans.count(x)) puts("?");
        else putchar(ans[x]),puts("");;
    }

    return 0;
}

C

先考慮一下無解的情況。

1.m為奇數肯定無解。這個很顯然，每條路徑長度都要是偶數，每條邊都要走恰好一遍。顯然邊數為偶數
2.如果存在某個點的度數為偶數，肯定無解。考慮一個點肯定要作為恰好一條路徑的端點，在這條路徑中這個點被走了奇數次。而其他的每條路徑這個點肯定都被走了偶數次。所以這個點的度數肯定為奇數。

然後先不考慮路徑長度為偶數的問題。那麼只要建一個虛點，向所有點連一條虛邊，這個每個點的度數都是偶數。跑一邊歐拉迴路，刪掉虛點和虛邊。就得到了一個答案。

然後考慮如何處理長度為偶數的限制。如果我們把邊兩兩配對建一個新圖(因為邊數為偶數，所以一定可以做到)，再按照上面的方法跑。最後把邊拆回成原來的邊即可。

然後考慮如何將邊配對。先建立一棵\(dfs\)樹,先讓子樹處理完子樹內部的邊。子樹可能無法恰好配對，當前可以處理的邊就有子樹內沒能處理掉的邊、與當前點相連的非樹邊、與父親相連的邊。儘量進行配對，如果無法完全配對就將剩下的那條邊(必須是與父親相連的那條)傳回給父親處理。

//@Author: wxyww
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
#include<map>
#include<string>
using namespace std;
typedef long long ll;
const int N = 2000000 + 10;
ll read() {
    ll x = 0,f = 1; char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9') {x = x * 10 + c - '0',c = getchar();}
    return x * f;
}
int du[N];
struct node {
    int u,v,nxt,id,id2;
}e[N];
struct NODE {
    int u,v,id1,id2;
};
queue<NODE>q;
int head[N],ejs = 1;
void add(int u,int v,int id,int id2) {
    e[++ejs].v = v;e[ejs].u = u;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].id = id;e[ejs].id2 = id2;
}
int viss[N],n,m,vis[N],dep[N];
int dfs(int u,int fa) {
    int now = 0;
    vis[u] = 1;
    for(int i = head[u];i;i = e[i].nxt) {
        if((i ^ 1) == fa) continue;
        int v = e[i].v;
        if(!vis[v]) {
            dep[v] = dep[u] + 1;
            int k = dfs(v,i);
            if(!k) {    viss[e[i].id] = 1;continue;}
            if(now) {
                q.push((NODE){e[k].v,e[now].v,e[k].id,e[now].id});
                now = 0;
            }
            else now = k;
        }
        else {
            if(dep[v] < dep[u]) continue;
            if(viss[e[i].id]) continue;
            if(now) {
                q.push((NODE){e[i].v,e[now].v,e[i].id,e[now].id});
                now = 0;
            }
            else now = i;
        }
        viss[e[i].id] = 1;
    }
    if(now) {
        q.push((NODE){e[fa ^ 1].v,e[now].v,e[fa].id,e[now].id});
        return 0;
    }
    return fa;
}
int vise[N],top,ans[N];
void Eur(int u) {
    for(int &i = head[u];i;i = e[i].nxt) {
        if(vise[i >> 1]) continue;
        vise[i >> 1] = 1;
        int v = e[i].v;
        int tmp = i;
        Eur(v);
        ans[++top] = e[tmp].id2;ans[++top] = e[tmp].id;
    }
}
int main() {
    n = read(),m = read();
    if(m & 1) return puts("0"),0;

    for(int i = 1;i <= m;++i) {
        int u = read(),v = read();
        du[u]++;du[v]++;
        add(u,v,i,0);add(v,u,i,0);
    }

    for(int i = 1;i <= n;++i) if(!(du[i] & 1)) return puts("0"),0;
    puts("1");

    dep[1] = 1;
    dfs(1,0);

    ejs = 1;memset(head,0,sizeof(head));

    while(!q.empty()) {
        NODE k = q.front();q.pop();
        add(k.u,k.v,k.id1,k.id2);
        add(k.v,k.u,k.id2,k.id1);
    }



    for(int i = 1;i <= n;++i) add(n + 1,i,-1,-1),add(i,n + 1,-1,-1);

    Eur(n + 1);

    for(int l = 1,r;l <= top;l = r + 1) {
        while(ans[l] == -1 && l <= top) ++l;
        if(l > top) break;
        r = l + 1;
        while(ans[r] != -1 && r <= top) ++r;
        printf("%d ",r - l);
        for(int i = l;i <= r - 1;++i) printf("%d ",ans[i]);
        
        puts("");
    }
    return 0;
}

總結

一定要造大數據測試程式。
註意細節。
認真讀題，get到全部條件。

期望得分:100+42+0=142
實際得分:7+22+0=29

嗚嗚嗚~


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • Python 入門之 文件
    Python 入門之 文件 1、文件操作 找到文件位置 雙擊打開 進行一些操作 r—read(讀) w—write(寫) a—追加 rd 讀位元組 wd 清空寫，寫位元組 ad 追加寫(位元組) r+ 讀寫 w+ 寫讀 a+ 追加讀 關閉文件 open() ： 打開 ，open通過python控制操作系統 ...
  • JMeter用戶參數
    壓測的時候，經常需要使用動態參數，即每次請求的參數不一樣，這樣才能更好的模擬真實的用戶請求 我們首先能想到的也是最常見的就是用戶ID 1. 用戶參數 我們可以定義一個變數，然後指定多個值，這樣每次請求的時候都會順序迴圈去取這些值。通過${variable}取值。 具體參見官方文檔，上面寫的比較詳盡， ...
  • 輸入和輸出處理
    Java I/O文件 文件記憶體 》程式 》記憶體鍵盤 控制台 文件 什麼是文件？ 相關記錄或放在一起的數據的集合 文件一般存儲在哪裡？ 磁碟，u盤，移動硬碟 Java程式如何訪問文件屬性？ JAVA API:java.io.File類 File類訪問文件屬性 File類 》創建文件對象 》操作文件或目 ...
  • SAP壓縮excel併發送mail案例
    SAP壓縮excel產生zip文件後作為附件發送mail案例. ...
  • ERROR: Could not install packages due to an EnvironmentError: [Errno 13] Permission denied: '/Library/Python/2.7/site-packages/itsdangerous' Consider using the `--user` option or check the per
    近期練習flask寫個blog， 安裝flask擴展時 報ERROR: Could not install packages due to an EnvironmentError: [Errno 13] Permission denied: '/Library/Python/2.7/site-pac ...
  • effective java 3th 序
    effective java 3th 序，java語言的簡單與複雜，以及本書出現的理由 ...
  • python面試題之如何解決驗證碼的問題，用什麼模塊，聽過哪些人工打碼平臺？
    如何解決驗證碼的問題，用什麼模塊，聽過哪些人工打碼平臺？ PIL、pytesser、tesseract模塊 平臺的話有：（打碼平臺特殊，不保證時效性） 雲打碼 掙碼 斐斐打碼 若快打碼 超級鷹本文首發於Python黑洞網，博客園同步更新 ...
  • Spring Cloud Zuul的動態路由怎樣做？集成Nacos實現很簡單
    一、說明 網關的核心概念就是路由配置和路由規則，而作為所有請求流量的入口，在實際生產環境中為了保證高可靠和高可用，是儘量要避免重啟的，所以實現動態路由是非常有必要的；本文主要介紹實現的思路，並且以 為數據源來講解   二、實現要點 要實現動態路由只需關註下麵4個點 1. 網關啟動時， 的數 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類