A - Odd Position Sum?

#1.奇數數位和

#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 1e4 + 10;
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n;cin>>n;int sum=0,x;for(int i=1;i<=n;i++){cin>>x;if(i&1)sum+=x;}cout<<sum<<endl;return 0;
}

B - Four Hidden??

?#1.暴力判斷即可,遇到#可任意匹配

#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 1e4 + 10;
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);string s1,s2;cin>>s1>>s2;int n=s1.length(),m=s2.length();s1="#"+s1;s2="#"+s2;for(int i=1;i+m-1<=n;i++){if(s1[i]==s2[1]||s1[i]=='?'){int j=i;int cnt=0;for(int j=i;j<=i+m-1;j++){if(s1[j]=='?'||s1[j]==s2[j-i+1])cnt++;}if(cnt==m){cout<<"Yes"<<endl;return 0;}}}cout<<"No"<<endl;return 0;
}

?C - 403 Forbidden

#1.set的簡單應用

#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 2e6+ 10;
set<pair<int,int>>st;
bool vis[N];
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int n,m,q;cin>>n>>m>>q;int ty,x,y;while(q--){cin>>ty;if(ty==1){cin>>x>>y;st.insert({x,y});}else if(ty==2){cin>>x;vis[x]=true;}else{cin>>x>>y;if(vis[x])cout<<"Yes"<<endl;else{if(st.count({x,y}))cout<<"Yes"<<endl;else cout<<"No"<<endl;}}}return 0;
}

D - Forbidden Difference?

給一個序列，我們需要刪除一些元素，讓剩下元素滿足任意兩個差的絕對值不等于d，問刪的最小值

#1.給定ai和d的值域都很小，可以開一個1e6的桶，來記錄ai中每個值出現的次數

#2.注意到當差的絕對值為d時，在1e6的范圍中是以d為步幅遞增的，也就是同余的，考慮將數對d取模?，單獨存在一個vector中,存在vector的中的是出現次數

#3.于是問題變成了一個經典dp問題--相鄰不取取最大，最后拿總數減剩下的就是答案（特判d==0）

#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 1e6+10;
const int M=1e6;
int cnt[N];
int a[N];
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n,d;cin>>n>>d;for(int i=1;i<=n;i++){cin>>a[i];cnt[a[i]]++;}if(d==0){int sz=0;for(int i=0;i<=M;i++){sz+=cnt[i]>0;}cout<<n-sz<<endl;return 0;}int sum=0;for(int i=0;i<d;i++){vector<int>b(1,0);for(int j=i;j<=M;j+=d){b.push_back(cnt[j]);}int sz=b.size()-1;vector<int>dp(sz+1,-1);dp[1]=b[1];if(sz>=2)dp[2]=max(dp[1],b[2]);for(int j=3;j<=sz;j++){dp[j]=max(dp[j-1],dp[j-2]+b[j]);}sum+=dp[sz];}cout<<n-sum<<endl;return 0;
}

?E - Forbidden Prefix

給兩個字符串集合x和y，q次操作，操作1是向x中添加字符串，操作2是對y中添加字符串，每次添加后輸出y中不以x中字符串為前綴的字符串

#1.求解字符串前綴問題考慮字典樹，要維護e數組，即有多少字符串經過該節點，每次要輸出的就是e[0]

#2.對操作1的刪除，有兩種情況，一種是添加的這個字符串它的前綴已經在x中出現，那就不用考慮，可以用vis標記x中字符串結尾，經過vis不為0的節點，說明前綴出現過。另一種是從未出現過，那就要將經過過該節點的節點都要減去這個節點的e值，代表這個前綴已經刪除

#3.接下來是向y中添加字符串，判斷路徑是否經過x的前綴即可，用vis判斷

#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N = 1e5 + 10;
int nxt[30*N][26];
int vis[30*N],cnt=0,sz=0,l,e[30*N];
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int q,ty;cin>>q;string s;while(q--){cin>>ty;if(ty==1){cin>>s;l=s.length();int now=0;bool tag=true;for(int i=0;i<l;i++){int x=s[i]-'a';if(!nxt[now][x])nxt[now][x]=++cnt;now=nxt[now][x];if(vis[now])tag=false;}vis[now]=1;if(tag){int y=0;e[y]-=e[now];for(int i=0;i<l;i++){int x=s[i]-'a';y=nxt[y][x];e[y]-=e[now];}}}else{cin>>s;l=s.length();int now=0;bool tag=true;for(int i=0;i<l;i++){int x=s[i]-'a';if(!nxt[now][x])nxt[now][x]=++cnt;now=nxt[now][x];if(vis[now])tag=false;}if(tag){now=0;e[now]++;for(int i=0;i<l;i++){int x=s[i]-'a';now=nxt[now][x];e[now]++;}}}cout<<e[0]<<endl;}return 0;
}

F - Shortest One Formula?

用一些1和+，*來構成一個表達式，使其結果為n，求最短表達式

#1.n只有2000，考慮暴力遞推，由于一個加法表達式和一個乘法表達式相乘時加法表達式需要加括號，那就將加法與乘法分開考慮，給f[i]表示最后一次操作是加法結果是i的字符串，g[i]表示最后一次操作時乘法結果時i的字符串

#2.從1遞推到n，特判1，11，111，1111，其他的遞推到i是，分解i為x+y后x*y，一一枚舉，更新f[i]與g[i]

#include<iostream>
#include<vector>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<stack>
#include<array>
#include<cmath>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<iomanip>
using namespace std;
using ll = long long;
using llu = unsigned long long;
const ll inf = 0x3f3f3f3f3f3f3f3fll;
const ll MIN = -9187201950435737472ll;
ll mod = 1e9 + 7;
ll base = 131;
const int N =2e3+10;
string f[N],g[N];
int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n;cin>>n;for(int i=1;i<=n;i++){if(i==1){f[i]="1";g[i]="1";}else if(i==11){f[i]="11";g[i]="11";}else if(i==111){f[i]="111";g[i]="111";}else if(i==1111){f[i]="1111";g[i]="1111";}else{f[i]=f[1]+"+"+f[i-1];for(int x=1;x+x<=i;x++){int y=i-x;if(f[x].size()+f[y].size()+1<f[i].size()){f[i]=f[x]+"+"+f[y];}if(f[x].size()+g[y].size()+1<f[i].size()){f[i]=f[x]+"+"+g[y];}if(g[x].size()+f[y].size()+1<f[i].size()){f[i]=g[x]+"+"+f[y];}if(g[x].size()+g[y].size()+1<f[i].size()){f[i]=g[x]+"+"+g[y];}}g[i]="("+f[i]+")"+"*"+g[1];for(int x=1;x<=i/x;x++){if(i%x)continue;int y=i/x;if(f[x].size()+f[y].size()+5<g[i].size()){g[i]="("+f[x]+")"+"*"+"("+f[y]+")";}if(f[x].size()+g[y].size()+3<g[i].size()){g[i]="("+f[x]+")"+"*"+g[y];}if(g[x].size()+f[y].size()+3<g[i].size()){g[i]=g[x]+"*"+"("+f[y]+")";}if(g[x].size()+g[y].size()+1<g[i].size()){g[i]=g[x]+"*"+g[y];}}}}if(f[n].size()<g[n].size()){cout<<f[n]<<endl;}else cout<<g[n]<<endl;return 0;
}

?

?

?