AC修煉計劃（AtCoder Regular Contest 180） A~C

A - ABA and BAB

A - ABA and BAB (atcoder.jp)

這道題我一開始想復雜了，一直在想怎么dp，沒注意到其實是個很簡單的規律題。

我們可以發現我們住需要統計一下類似ABABA這樣不同字母相互交替的所有子段的長度，而每個字段的的情況有（長度+1）/2種，最后所有字段情況的乘積就是最終答案。

#pragma GCC optimize(3)  //O2優化開啟
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
// const int mod=1e9+7;
const int MX=0x3f3f3f3f3f3f3f3f; 
//inline int read()                     //快讀
//{
//    int xr=0,F=1; char cr;
//    while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
//    while(cr>='0'&&cr<='9')
//        xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
//    return xr*F;
//}
//void write(int x)                     //快寫
//{
//    if(x<0) putchar('-'),x=-x;
//    if(x>9) write(x/10); putchar(x%10+'0');
//}
// 比 unordered_map 更快的哈希表
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// struct chash {
//     int operator()(int x) const { return x ^ RANDOM; }
// };
// typedef gp_hash_table<int, int, chash> hash_t;
constexpr ll mod = 1e9 + 7;                                //此處為自動取模的數
class modint{ll num;
public:modint(ll num = 0) :num(num % mod){}ll val() const {return num;}modint pow(ll other) {modint res(1), temp = *this;while(other) {if(other & 1) res = res * temp;temp = temp * temp;other >>= 1;}return res;}constexpr ll norm(ll num) const {if (num < 0) num += mod;if (num >= mod) num -= mod;return num;}modint inv(){ return pow(mod - 2); }modint operator+(modint other){ return modint(num + other.num); }modint operator-(){ return { -num }; }modint operator-(modint other){ return modint(-other + *this); }modint operator*(modint other){ return modint(num * other.num); }modint operator/(modint other){ return *this * other.inv(); }modint &operator*=(modint other) { num = num * other.num % mod; return *this; }modint &operator+=(modint other) { num = norm(num + other.num); return *this; }modint &operator-=(modint other) { num = norm(num - other.num); return *this; }modint &operator/=(modint other) { return *this *= other.inv(); }friend istream& operator>>(istream& is, modint& other){ is >> other.num; other.num %= mod; return is; }friend ostream& operator<<(ostream& os, modint other){ other.num = (other.num + mod) % mod; return os << other.num; }
};int n;
string s;
void icealsoheat(){cin>>n;cin>>s;s=" "+s;int res=1;modint ans=1;for(int i=2;i<=n;i++){if(s[i]!=s[i-1]){res++;}else{if(res>=3){ans*=(res+1)/2;}res=1;}}if(res>=3){ans*=(res+1)/2;}cout<<ans;
}
signed main(){ios::sync_with_stdio(false);          //int128不能用快讀！！！！！！cin.tie();cout.tie();int _yq;_yq=1;// cin>>_yq;while(_yq--){icealsoheat();}
}
//
//???             ???????????
//????????????? ???????????
//??????????????????????????
//????????????????????? ?????
//???????????????????????
//??????????????????? ????
//????????????????????????
//????????????????????????
//???????????????????????
//??????????????????????
//??????????????
//????????????
//

B - Improve Inversions

B - Improve Inversions (atcoder.jp)

這題確實不好想，但是get到點兒了就會覺得其實也不難。

我們需要盡可能的把逆序對最大化，從樣例三我們可以發現，我們不妨確立左邊一個要交換的下標i，然后找下標大于等于i+k，數值從大到小的找小于ai的數字，并依次與i的數字進行交換。為了盡可能減少替換的影響，我們按數值從小到大的次序去找這個下標i，從而參與上述的交換。因為我們是按從小到大的順序的，所以小的數字參與交換并不會影響后面大的數字該交換的逆序對。

#pragma GCC optimize(3)  //O2優化開啟
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
// const int mod=1e9+7;
const int MX=0x3f3f3f3f3f3f3f3f; 
//inline int read()                     //快讀
//{
//    int xr=0,F=1; char cr;
//    while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
//    while(cr>='0'&&cr<='9')
//        xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
//    return xr*F;
//}
//void write(int x)                     //快寫
//{
//    if(x<0) putchar('-'),x=-x;
//    if(x>9) write(x/10); putchar(x%10+'0');
//}
// 比 unordered_map 更快的哈希表
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// struct chash {
//     int operator()(int x) const { return x ^ RANDOM; }
// };
// typedef gp_hash_table<int, int, chash> hash_t;
// constexpr ll mod = 1e9 + 7;                                //此處為自動取模的數
// class modint{
//     ll num;
// public:
//     modint(ll num = 0) :num(num % mod){}//     ll val() const {
//         return num;
//     }//     modint pow(ll other) {
//         modint res(1), temp = *this;
//         while(other) {
//             if(other & 1) res = res * temp;
//             temp = temp * temp;
//             other >>= 1;
//         }
//         return res;
//     }//     constexpr ll norm(ll num) const {
//         if (num < 0) num += mod;
//         if (num >= mod) num -= mod;
//         return num;
//     }//     modint inv(){ return pow(mod - 2); }
//     modint operator+(modint other){ return modint(num + other.num); }
//     modint operator-(){ return { -num }; }
//     modint operator-(modint other){ return modint(-other + *this); }
//     modint operator*(modint other){ return modint(num * other.num); }
//     modint operator/(modint other){ return *this * other.inv(); }
//     modint &operator*=(modint other) { num = num * other.num % mod; return *this; }
//     modint &operator+=(modint other) { num = norm(num + other.num); return *this; }
//     modint &operator-=(modint other) { num = norm(num - other.num); return *this; }
//     modint &operator/=(modint other) { return *this *= other.inv(); }
//     friend istream& operator>>(istream& is, modint& other){ is >> other.num; other.num %= mod; return is; }
//     friend ostream& operator<<(ostream& os, modint other){ other.num = (other.num + mod) % mod; return os << other.num; }
// };int n,k;
int a[200005];
int p[200005];
vector<PII>ans;
void icealsoheat(){cin>>n>>k;int bns=0;for(int i=1;i<=n;i++)cin>>a[i],p[a[i]]=i;for(int i=1;i<=n;i++){int id=p[i];int x=i;for(int j=i-1;j>=1;j--){if(p[j]>=id+k){// cout<<p[x]<<":::"<<p[j]<<"\n";ans.push_back({p[x],p[j]});a[id]=j;a[p[j]]=x;swap(p[x],p[j]);x=j;}}}cout<<ans.size()<<"\n";for(auto [i,j]:ans){cout<<i<<" "<<j<<"\n";}// for(int i=1;i<=n;i++){//     cout<<a[i]<<" ";// }}
signed main(){ios::sync_with_stdio(false);          //int128不能用快讀！！！！！！cin.tie();cout.tie();int _yq;_yq=1;// cin>>_yq;while(_yq--){icealsoheat();}
}
//
//???             ???????????
//????????????? ???????????
//??????????????????????????
//????????????????????? ?????
//???????????????????????
//??????????????????? ????
//????????????????????????
//????????????????????????
//???????????????????????
//??????????????????????
//??????????????
//????????????
//

C - Subsequence and Prefix Sum

C - Subsequence and Prefix Sum (atcoder.jp)

一道非常巧妙的dp題，他的狀態轉移非常的奇妙。

我們考慮前i位的數字對后面數字的貢獻值。可以分成兩種情況。

1.第i位數字沒有被選中

2.第i位數字被選中

當第i位數字被選中時，每一個位數i它所能合成的狀態數字都對后面i+1到n的數字有相應的貢獻。而這里面0的情況比較特殊，如果第i位的合成數字是0，其實不會改變下一個選中的數字。

這里面有一種情況比較特殊

例如1 -1 5 5 .........

這里我們會發現，我們選擇1和-1后，選擇第3個5和第4個5的情況是重復的，所以我們要想辦法將它去重。

#pragma GCC optimize(3)  //O2優化開啟
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
// const int mod=1e9+7;
const int MX=0x3f3f3f3f3f3f3f3f; 
//inline int read()                     //快讀
//{
//    int xr=0,F=1; char cr;
//    while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
//    while(cr>='0'&&cr<='9')
//        xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
//    return xr*F;
//}
//void write(int x)                     //快寫
//{
//    if(x<0) putchar('-'),x=-x;
//    if(x>9) write(x/10); putchar(x%10+'0');
//}
// 比 unordered_map 更快的哈希表
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// struct chash {
//     int operator()(int x) const { return x ^ RANDOM; }
// };
// typedef gp_hash_table<int, int, chash> hash_t;
constexpr ll mod = 1e9 + 7;                                //此處為自動取模的數
class modint{ll num;
public:modint(ll num = 0) :num(num % mod){}ll val() const {return num;}modint pow(ll other) {modint res(1), temp = *this;while(other) {if(other & 1) res = res * temp;temp = temp * temp;other >>= 1;}return res;}constexpr ll norm(ll num) const {if (num < 0) num += mod;if (num >= mod) num -= mod;return num;}modint inv(){ return pow(mod - 2); }modint operator+(modint other){ return modint(num + other.num); }modint operator-(){ return { -num }; }modint operator-(modint other){ return modint(-other + *this); }modint operator*(modint other){ return modint(num * other.num); }modint operator/(modint other){ return *this * other.inv(); }modint &operator*=(modint other) { num = num * other.num % mod; return *this; }modint &operator+=(modint other) { num = norm(num + other.num); return *this; }modint &operator-=(modint other) { num = norm(num - other.num); return *this; }modint &operator/=(modint other) { return *this *= other.inv(); }friend istream& operator>>(istream& is, modint& other){ is >> other.num; other.num %= mod; return is; }friend ostream& operator<<(ostream& os, modint other){ other.num = (other.num + mod) % mod; return os << other.num; }
};int n,k;
int a[500005];
modint dp[105][5005];
modint sum[5005];
void icealsoheat(){cin>>n;for(int i=0;i<=20;i++)if(i!=10)sum[i]=1;for(int i=1;i<=n;i++)cin>>a[i];modint ans=1;for(int i=0;i<n;i++){dp[i][a[i]+1000]=dp[i][a[i]+1000]+sum[a[i]+10];sum[a[i]+10]=0;for(int j=0;j<=2000;j++){if(j==1000)continue;for(int o=i+1;o<=n;o++){// if(j+a[o]<0)cout<<"+++\n";if(j+a[o]<0)continue;dp[o][j+a[o]]+=dp[i][j];ans+=dp[i][j];}}for(int j=0;j<=20;j++){if(j!=10)sum[j]+=dp[i][1000];}}cout<<dp[2][1]<<"+++\n";cout<<ans;}
signed main(){ios::sync_with_stdio(false);          //int128不能用快讀！！！！！！cin.tie();cout.tie();int _yq;_yq=1;// cin>>_yq;while(_yq--){icealsoheat();}
}
//
//???             ???????????
//????????????? ???????????
//??????????????????????????
//????????????????????? ?????
//???????????????????????
//??????????????????? ????
//????????????????????????
//????????????????????????
//???????????????????????
//??????????????????????
//??????????????
//????????????
//

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/44641.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/44641.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/44641.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Postman中的API安全堡壘：全面安全性測試指南

Postman中的API安全堡壘：全面安全性測試指南

&#x1f6e1;? Postman中的API安全堡壘&#xff1a;全面安全性測試指南 在當今的數字化世界中&#xff0c;API安全性是保護數據和系統不可或缺的一環。Postman作為API開發和測試的領先工具&#xff0c;提供了多種功能來幫助開發者進行API安全性測試。本文將深入探討如何在Po…
閱讀更多...
交互式AI的新紀元：Transformer模型的革新應用

交互式AI的新紀元：Transformer模型的革新應用

交互式AI的新紀元&#xff1a;Transformer模型的革新應用 隨著人工智能技術的不斷進步&#xff0c;交互式人工智能&#xff08;AI&#xff09;逐漸成為提升用戶體驗的關鍵技術。Transformer模型&#xff0c;以其卓越的處理序列數據的能力&#xff0c;已成為推動交互式AI發展的…
閱讀更多...
利用 AI 解放雙手：把“賈維斯”帶進現實 | 開源專題 No.64

利用 AI 解放雙手：把“賈維斯”帶進現實 | 開源專題 No.64

Significant-Gravitas/AutoGPT Stars: 160k License: MIT AutoGPT 是開源 AI 代理生態系統的核心工具包。 提供構建、測試和委托 AI 代理的工具。AutoGPT 處于 AI 創新前沿&#xff0c;提供文檔、貢獻指南以及快速開始創建自己的代理。包含強大的組件如 Forge 和 Benchmark&…
閱讀更多...
【教程】Hexo 部署到 Github Page 后，自定義域名失效的問題

【教程】Hexo 部署到 Github Page 后，自定義域名失效的問題

目錄 前言&問題描述解決方案細節 前言&問題描述 近期給 Github Page 上托管的靜態網站映射了自定義域名&#xff08;aiproducthome.top&#xff09;&#xff0c;之后發現每次更新并部署 hexo 到 Github Page &#xff08;hexo d&#xff09;后就會出現自定義域名失效的…
閱讀更多...
探索SQL Server查詢優化的奧秘：數據庫查詢優化器深度解析

探索SQL Server查詢優化的奧秘：數據庫查詢優化器深度解析

探索SQL Server查詢優化的奧秘&#xff1a;數據庫查詢優化器深度解析 在數據庫管理的世界里&#xff0c;查詢優化器是確保查詢效率的關鍵組件。SQL Server的查詢優化器采用先進的算法&#xff0c;將用戶的SQL查詢轉換成高效的執行計劃。本文將深入探討SQL Server查詢優化器的工…
閱讀更多...
高效利用iCloud：全面指南與技術深度解析

高效利用iCloud：全面指南與技術深度解析

引言 在數字化時代&#xff0c;數據的同步、備份和跨設備協作變得尤為重要。蘋果公司的iCloud服務憑借其強大的云存儲和同步功能&#xff0c;為用戶提供了一個無縫的數據管理解決方案。本文將全面介紹如何高效利用iCloud&#xff0c;幫助用戶更好地管理數據、提升工作效率&…
閱讀更多...
Python如何進行游戲開發？

Python如何進行游戲開發？

使用Python進行游戲開發可以通過以下幾個步驟來實現。Python有多個游戲開發框架和庫&#xff0c;最常用的是Pygame。下面是一個簡要的指南&#xff0c;介紹如何使用Pygame進行游戲開發。 安裝Pygame 首先&#xff0c;你需要安裝Pygame庫。你可以使用pip進行安裝&#xff1a; …
閱讀更多...
前端如何去看藍湖

前端如何去看藍湖

首先加入團隊&#xff0c;在內容中我們可以看到點擊圖片&#xff0c;右邊出現的圖 包含了像素甚至有代碼&#xff0c;我們可以參考這個代碼。 那么在使用之前我們需要調整好像素&#xff0c;例如我們的像素寬為375&#xff0c;不用去管高&#xff0c;然后這個寬度我們可以去自…
閱讀更多...
QT——Excel實現自繪區域選擇邊框

QT——Excel實現自繪區域選擇邊框

文章目錄 一、自繪區域邊框1.1、效果展示2.2、問題整理2.2.1、重繪單元格選擇區2.2.2、選擇區域的大小 一、自繪區域邊框 1.1、效果展示 單選 多選 2.2、問題整理 2.2.1、重繪單元格選擇區 誤區: 繼承QStyledItemDelegate重寫paint,測試發現只能在單元格內繪制。 通過繼…
閱讀更多...
圖鳥UI框架在uni-app多端應用開發中的實踐與應用

圖鳥UI框架在uni-app多端應用開發中的實踐與應用

摘要&#xff1a; 隨著移動互聯網的蓬勃發展&#xff0c;跨平臺應用開發已成為行業趨勢。本文將探討圖鳥UI框架如何在uni-app開發環境下助力開發者高效構建多端應用&#xff0c;并通過具體案例展示其在實際項目中的應用效果。 一、引言 在移動應用開發領域&#xff0c;跨平臺…
閱讀更多...
Java | Leetcode Java題解之第228題匯總區間

Java | Leetcode Java題解之第228題匯總區間

題目&#xff1a; 題解&#xff1a; class Solution {public List<String> summaryRanges(int[] nums) {List<String> ans new ArrayList<>();for (int i 0, j, n nums.length; i < n; i j 1) {j i;while (j 1 < n && nums[j 1] num…
閱讀更多...
性能飆升的藝術：SQL Server數據庫優化的最佳實踐

性能飆升的藝術：SQL Server數據庫優化的最佳實踐

性能飆升的藝術&#xff1a;SQL Server數據庫優化的最佳實踐 在企業級應用中&#xff0c;數據庫性能往往是決定應用響應速度和用戶體驗的關鍵因素。SQL Server作為業界領先的關系型數據庫管理系統&#xff0c;提供了一系列的工具和策略來分析和優化數據庫性能。本文將詳細介紹…
閱讀更多...
Android 通用視頻組件開發

Android 通用視頻組件開發

背景 目前車機的多媒體App都是各自維護自己的UI視圖及基礎邏輯&#xff0c;會有不少重復代碼。并且大多數媒體App都會和本地多媒體有交互&#xff0c;所有媒體App都會接入到MediaCenter&#xff0c;沒有統一的接口會導致接入適配成本和維護成本比較高。所以希望能夠抽出公共基…
閱讀更多...
分享一個項目模板electron+vue+ts+vite

分享一個項目模板electron+vue+ts+vite

分享一個項目模板electronvuetsvite GitHub - xiugou798/electron-vue-ts-vite-template: electron-vue-ts-vite-templateelectron-vue-ts-vite-template. Contribute to xiugou798/electron-vue-ts-vite-template development by creating an account on GitHub.https://gith…
閱讀更多...
linux之內存泄漏分析

linux之內存泄漏分析

內存泄漏通常是指程序中動態分配的內存沒有被適時釋放&#xff0c;導致這部分內存在程序的生命周期內一直無法被再次利用。內存泄漏不會直接導致程序崩潰&#xff0c;所以通常不會生成core dump文件。然而&#xff0c;如果程序因為其他原因崩潰&#xff0c;那么core dump文件可…
閱讀更多...
弱電工程質量保修期是多久?

弱電工程質量保修期是多久?

弱電工程是電力工程的一個分類&#xff0c;弱電可以向人們提供照明用電和空調用電&#xff0c;為人們的生活帶來了極大的便利。弱電工程作為一類工程項目存在質量保證問題&#xff0c;在施工完成后需要進行質量檢修&#xff0c;施工隊應該向業主提供一定的質量保修期&#xff0…
閱讀更多...
java 數據庫連接池的種類和選型

java 數據庫連接池的種類和選型

文章目錄 1.引言數據庫連接池的重要性Java數據庫連接池的基本概念連接池需要注意的問題 2.數據庫連接池C3P0數據庫連接池C3P0的基本介紹C3P0的使用示例 DBCP數據庫連接池DBCP的基本介紹DBCP的使用示例 HikariCP數據庫連接池&#xff08;廣泛使用&#xff09;HikariCP的基本介紹…
閱讀更多...
LLM大模型應用中的安全對齊的簡單理解

LLM大模型應用中的安全對齊的簡單理解

LLM大模型應用中的安全對齊的簡單理解 隨著人工智能技術的不斷發展&#xff0c;大規模語言模型&#xff08;如GPT-4&#xff09;的應用越來越廣泛。為了保證這些大模型在實際應用中的性能和安全性&#xff0c;安全對齊&#xff08;Safe Alignment&#xff09;成為一個重要的概…
閱讀更多...
CentOS 7 編譯安裝 sqlite3

CentOS 7 編譯安裝 sqlite3

1. 下載 sqlite3 源碼 網址&#xff1a; https://www.sqlite.org/download.html [注]&#xff1a;可自行選擇版本&#xff0c;也可與筆者保持一致。 wget https://www.sqlite.org/2024/sqlite-autoconf-3460000.tar.gz2. 解壓編譯并安裝 解壓源碼包&#xff0c;并進入源碼…
閱讀更多...
實驗-ENSP實現防火墻區域策略與用戶管理

實驗-ENSP實現防火墻區域策略與用戶管理

目錄 實驗拓撲 自己搭建拓撲 實驗要求 實驗步驟 整通總公司內網 sw3配置vlan 防火墻配置IP 配置安全策略&#xff08;DMZ區內的服務器&#xff0c;辦公區僅能在辦公時間內&#xff08;9: 00- 18:00)可以訪問&#xff0c;生產區的設備全天可以訪問&#xff09; 配置nat策…
閱讀更多...
最新文章

Copyright @ 2022~2023