牛客IOI周賽28-普及組
String Game
簡單模擬，把第一個移到末尾，移動的次數x不超過n，直接從第x個字符開始輸出，然后輸出前面的數
類似的如果超過n個字符，每移動n個字符，相當于還是原字串，所以每次從\(x%n\)開始輸出，再輸出\(x%n\)的數
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
long long n,x;
string s;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>x;
cin>>s;
x%=n;
for(int i=x;i<n;++i) cout<<s[i];
for(int i=0;i<x;++i) cout<<s[i];
return 0;
}
Sequence Game
最長上升子序列（LIS）的變式
其實就是二維版LIS
定義\(dp[i][j]\)為前i個數，取值為第j個值的LIS
可以易得
\(dp_{i,j}=max(dp_{x,y}+1) (a[i][j]>a[x][y],x<=i,y<=k)\)
直接寫出來O(10^12)直接裂開，考慮降維（打擊）i維
這里的還有貪心的一點
對于相同的長度即\(dp[i][j]\)，末尾越小越好，
所以我們可以造一個陣列\(ed[i]\)意為LIS長度為i的最小結尾數
第i行，把\(a[j]\)與不同長度末尾比較，大了就可以連接成一個更長的LIS
然后還要考慮是否能更新\(ed[]\)
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int inf=1e9;
const int maxn=5e3+10;
int a[maxn];
int ed[maxn];//存盤長度為i，結尾最小的a的值
int dp[maxn];//記錄以a[i][j]結尾的最長長度
int k,n;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>k>>n;
for(int i=1;i<=n;++i) ed[i]=inf;//初始化
for(int i=1;i<=n;++i){
for(int j=1;j<=k;++j) cin>>a[j];
int p=0;
for(int j=1;j<=k;++j){
while(p<n && ed[p+1]<a[j]) ++p;//把a[j]和不同長度的末尾比較
dp[j]=p+1;//此時以a[j]為結尾的最長上升子序列為p+1
}
for(int j=1;j<=k;++j) ed[dp[j]]=min(ed[dp[j]],a[j]);//更新以dp[j]長度為結尾的，是選擇a[j]為結尾，還是原數為結尾
}
for(int i=n;i>=1;--i){//這個長度有值，則輸出
if(ed[i]!=inf){
cout<<i<<endl;
break;
}
}
return 0;
}
Simple Game
題目背景沒有鳥用，直接看輸出描述每個地鐵站能到達的編號最小的地鐵站的編號
反向建圖，那么每個點能到達，那么這樣就意味著
每個點遍歷時，直接把能到這個點的所有點都更新為這個點的編號，從編號1開始搜索即可，搜過的打標記不用搜
因為第一次被搜到的點記錄的一定為最小值
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int maxn=1e5+10;
int m;
bool book;
int head[maxn];
struct node{
int v,next;
}e[maxn];
int nr[maxn];
int cnt=0;
int in[maxn];
void add(int u,int v){
e[++cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int u,int topf){
nr[u]=topf;
for(int i=head[u];i;i=e[i].next)
if(nr[e[i].v]==0)dfs(e[i].v,topf);
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;memset(nr,0,sizeof(nr));
for(int i=1;i<=m;++i){
int u,v;cin>>u>>v;
add(v,u);
}
for(int i=1;i<=n;++i) if(nr[i]==0)dfs(i,i);
sort(nr+1,nr+1+n);
int last=0;bool book=0;
for(int i=1;i<=n;++i){
if(nr[i]==last) continue;
last=nr[i];book=1;
cout<<nr[i]<<" ";
}if(book==0) cout<<1<<endl;
return 0;
}
Sweet Game
雖然是個取值題，但實質是一個構造題，構造一個序列使得值最大，構造時就求值，不用求出序列
思路
直接將第\(n\)個糖加入序列（因為它右邊的糖無糖可吃，滿足題意直接加）
那么此時\(n-1\)個糖也滿足加入序列的條件（因為第\(n\)個糖吃完了）
以此類推，所以從后往前列舉，會使得\(i+1~n\)的糖都被吃了，第\(i\)個糖也滿足被吃條件
而加入序列，根據題意則會有兩種情況
設\(a[]\)為糖的甜度，\(b[]\)為糖的變化值
-
加入整個序列的左邊（說明\(i+1\) ~ \(n\)的糖將要吃完）
此時\(ans=\sum_{j=i}^{n}b[i]+ans+a[i]\) -
加入整個序列的右邊(說明\(i+1\) ~ \(n\)的糖已經吃完)
此時\(ans=ans+a[i]+(n-i)*b[i]\)
其實為什么不能從1開始吃
會發現先吃了第1顆糖之后，只能吃第\(2\) ~ \(n\)顆糖
那么接下來只能吃2顆糖，吃完后，又只能吃第\(3\) ~ \(n\)顆糖
以此類推，構造出來的序列是唯一的，所以很大可能不是解
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n;
const int maxn=2e5+10;
long long ans=0;
long long a[maxn],b[maxn];
inline long long read()
{
int 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<<1)+(x<<3)+c-'0';
c=getchar();
}
return x*f;
}
int main(){
n=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=n;++i) b[i]=read();
for(int i=n;i>=1;--i) {
long long nxt=max(ans+sum+a[i],ans+a[i]+(n-i)*b[i]);//ans+sum+a[i]為插入整個序列左邊的情況，ans+a[i]+(n-i)*b[i]為插入右邊
ans=nxt;
sum+=b[i];//記錄當前序列的整體▲d
}
cout<<ans<<endl;return 0;
}
賽后總結
1.讀清題意
2.不要死磕一道題，實在磕不出來趕緊換
3.嘗試將考場題轉化為做過的題
ZFY AK IOI
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/297734.html
標籤：其他
上一篇：淺談探索式測驗
下一篇：AcWing 第15場周賽