先总结一下,这套题有 dfs,bfs,01背包,暴力,模拟,思维,签到
总体来说,是新生赛的水平,比较费体力,知识点不难,做不出来也是自己的代码有些小错误(看题解的时候发现思路一样,代码都几乎一样,就是几个小点eg:int -> long long)
《落花》&&《红衣集》
模拟题,注意边界就行
#include<iostream> #include<algorithm> #include<map> #include<algorithm> #include<utility> #include<vector> #define PII pair<int,int> #define rep(i,a,b) for(int i=a;i<=b;i++) #define int long long using namespace std; const int N = 1e5+10; int a[N],b[N]; // 美丽 价格 signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin>>n; rep(i,1,n-1) cin>>b[i]; rep(i,1,n-1) cin>>a[i]; int sp=a[1],val=b[1]; for(int i=1;i<n;i++) { if(a[i]>sp) { sp = max(a[i],a[i+1]); if(a[i]==a[i+1]) val += min(b[i],b[i+1]); else if(a[i]>a[i+1]) val +=b[i]; else val +=b[i+1]; i++; } } cout<<val<<endl; return 0; }
留春春不住，春归人寂寞。
最短路
spfa,dijkstra啥的都行,反正我是学过一遍这几个最短路之后,只是会用,也不知道我写的叫啥…
#include<iostream> #include<algorithm> #include<map> #include<algorithm> #include<utility> #include<vector> #include<queue> #include<cstring> #define int long long #define PII pair<int,int> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int N = 1e6+10; const int MOD = 1e9+7; int e[N],h[N],ne[N],val[N],id; void add(int a,int b,int c) { e[id]=b,val[id]=c,ne[id]=h[a],h[a]=id++; } int dist[N]; bool vis[N]; void sol() { memset(vis,false,sizeof vis); memset(h,-1,sizeof h); memset(dist,0x6f,sizeof dist); int n,m,u,v,t; cin>>n>>m; rep(i,1,m) { cin>>u>>v>>t; add(u,v,t); add(v,u,t); } queue<int>q; dist[1]=0; q.push(1); while(q.size()) { int u = q.front(); q.pop(); vis[u]=false; for(int i=h[u];i!=-1;i=ne[i]) { int v = e[i]; if(dist[v]>dist[u]+val[i]) { dist[v]=dist[u]+val[i]; if(!vis[v]) { q.push(v); vis[v]=true; } } } } cin>>m; while(m--) { cin>>t; cout<<dist[t]<<endl; } // rep(i,1,n) { // cout<<"dist["<<i<<"]:"<<dist[i]<<endl; // } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T=1; // cin>>T; while(T--) sol(); return 0; }
厌风风不定，风起花萧索。
二位前缀和,字符串用数字标记(我这里用的
map<string,int>)
#include<iostream> #include<algorithm> #include<map> #include<algorithm> #include<utility> #include<vector> #include<queue> #include<cstring> #define int long long #define PII pair<int,int> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int N = 1e3+10; map<string,int>mp; int id,a[N][N]; void sol() { int n,x; string s; cin>>n; rep(i,1,n) { cin>>s>>x; int t; if(!mp.count(s)) { mp[s]=++id; } t = mp[s]; a[i][t]+=x; } rep(i,1,n) { rep(j,1,id) { a[i][j]+=a[i-1][j]; } } int q,l,r; cin>>q; while(q--) { cin>>l>>r>>s; if(!mp.count(s)) { cout<<0<<endl; continue; } int t = mp[s]; cout<<a[r][t]-a[l-1][t]<<endl; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T=1; // cin>>T; while(T--) sol(); return 0; }
既兴风前叹，重命花下酌。
本人比较笨,只知道其中几个,剩下的打表一个个试
#include<iostream> #include<algorithm> #include<map> #include<algorithm> #include<utility> #include<vector> #define PII pair<int,int> #define rep(i,a,b) for(int i=a;i<=b;i++) #define int long long using namespace std; const int N = 1e7+10; const int MOD = 1e9+7; signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout<<"FTFTTTF"<<endl; return 0; }
劝君尝绿醅，教人拾红萼。
签到快乐
#include<iostream> #include<algorithm> #include<map> #include<algorithm> #include<utility> #include<vector> #define PII pair<int,int> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int N = 1e5+10; vector<PII>ve; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout<<"\"xi\\nan\\min\\zu\\da\\xue,zhen\\mei!\""; return 0; }
桃飘火焰焰，梨堕雪漠漠。
把游戏分成两部分,必玩的直接累加时间,非必玩的排个序,从小往大加上剩下的
k-m个游戏
#include<iostream> #include<algorithm> #include<map> #include<algorithm> #include<utility> #include<vector> #define PII pair<int,int> #define rep(i,a,b) for(int i=a;i<=b;i++) #define int long long #define pi acos(-1) using namespace std; const int N = 1e5+10; const int MOD = 1e9+7; int a[N]; int b[N]; map<int,int>mp; signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m,k,x,an=0; cin>>n>>m>>k; rep(i,1,n) cin>>a[i]; rep(i,1,m) cin>>x,an+=a[x],mp[x]=1; int q=0; rep(i,1,n) if(!mp.count(i)) b[++q]=a[i]; sort(b+1,b+1+q); for(int i=1;i<=k-m;i++) an+=b[i]; cout<<an<<endl; return 0; }
独有病眼花，春风吹不落。
并查集(看了眼题解的做法),但是我看了一眼数据,把棋牌扩大两倍,那么对每一步进行
dfs搜索,好像也能过,不知道哪里写错了,最后过了一半数据
// 并查集 #include<iostream> #include<algorithm> #include<map> #include<algorithm> #include<utility> #include<vector> #include<queue> #include<cstring> #define int long long #define PII pair<int,int> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int N = 1e7+10; const int dx[]={0,0,1,-1}; const int dy[]={1,-1,0,0}; int fa[N]; int find(int x) { return fa[x]==x?x:(fa[x]=find(fa[x])); } void merge(int i,int j) { int x=find(i); int y=find(j); fa[x]=y; } bool sub(int a,int b) { int x = find(a); int y = find(b); return x==y; } void sol() { int n,m,x,y; char c; bool f=true; cin>>n>>m; n++;n++; rep(i,1,n*n) fa[i]=i; for(int i=1;i<=m;i++){ cin>>x>>y>>c; int a=x*n+y,b; int xx,yy; if(c=='D') b=(x+1)*n+y,xx=x+1,yy=y; else b=x*n+y+1,xx=x,yy=y+1; // cout<<"x:"<<x<<" y:"<<y<<endl; // cout<<"xx:"<<xx<<" yy:"<<yy<<endl; // cout<<"fa[1]:"<<fa[a]<<" fa[2]:"<<fa[b]<<endl; // cout<<"===="<<endl; if(f&&sub(a,b)) { f = false; cout<<i<<endl; } merge(a,b); } if(f) cout<<"draw"<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T=1; while(T--) sol(); return 0; }
#include<iostream> #include<algorithm> #include<map> #include<algorithm> #include<utility> #include<vector> #include<queue> #include<cstring> #define int long long #define PII pair<int,int> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int N = 4e3+10; const int dx[]={0,0,1,-1}; const int dy[]={1,-1,0,0}; bool vis[N][N]; bool a[N][N]; int n,m; bool f=false; void dfs(int x,int y,int lx,int ly) { // cout<<"x:"<<x<<" y:"<<y<<endl; if(vis[x][y]) { f=true; return ; } vis[x][y]=true; for(int i=0;i<=3;i++) { int xx = x+dx[i]; int yy = y+dy[i]; if(xx<1||xx>n||yy<1||yy>n) continue; if(!a[xx][yy]) continue; if(xx==lx&&yy==ly) continue; dfs(xx,yy,x,y); if(f) return ; } } void sol() { int x,y; char c; memset(a,0,sizeof a); cin>>n>>m; n+=3; n*=2; rep(i,1,m) { cin>>x>>y>>c; x<<=1; y<<=1; if(c=='D') { a[x][y]=true; a[x+1][y]=true; a[x+2][y]=true; }else { a[x][y]=true; a[x][y+1]=true; a[x][y+2]=true; } if(!f) { memset(vis,false,sizeof vis); dfs(x,y,0,0); if(f) cout<<i<<endl; } // cout<<"i:"<<i<<endl; // rep(j,1,n) { // rep(k,1,n) { // cout<<a[j][k]<<" "; // } // cout<<endl; // } // cout<<endl; } if(!f) cout<<"draw"<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T=1; while(T--) sol(); return 0; }
荷池堪作镜，盈盈可鉴心。
做个预处理,从前往后推吧,开个
1e7的数组不会爆
#include<iostream> #include<algorithm> #include<map> #include<algorithm> #include<utility> #include<vector> #define PII pair<int,int> #define rep(i,a,b) for(int i=a;i<=b;i++) #define int long long using namespace std; const int N = 1e7+10; const int MOD = 1e9+7; int f[N]; void init() { f[1]=1;f[2]=2;f[3]=3; for(int i=4;i<=10000000;i++) { f[i]=(f[i-1]+f[i-3])%MOD; } } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); init(); int x; cin>>x; cout<<f[x]<<endl; return 0; }
荷香堪筑梦，鸳鸯和月寻。
dfs因为是只有有过的就行
#include<iostream> #include<algorithm> #include<map> #include<algorithm> #include<utility> #include<vector> #include<queue> #include<cstring> #define int long long #define PII pair<int,int> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int N = 1e3+10; string s[N]; bool f=false; int n,m,x; void dfs(int po,int cel) { if(!cel) { f=true; return ; } for(int j=1;j<=m;j++) { if(s[cel][j]=='.'&&abs(po-j)<=x) { dfs(j,cel-1); if(f) return ; } } } void sol() { cin>>n>>m>>x; rep(i,1,n) cin>>s[i],s[i]="_"+s[i]; rep(j,1,m) { if(s[n][j]=='a') { dfs(j,n-1); } } cout<<(f?"yes":"no")<<endl; } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T=1; // cin>>T; while(T--) sol(); return 0; }
荷香莫深湎，终付秋风落。
读入用
while(cin>>s),然后无脑判断:w就行
#include<iostream> #include<algorithm> #include<map> #include<algorithm> #include<utility> #include<vector> #define PII pair<int,int> #define rep(i,a,b) for(int i=a;i<=b;i++) #define int long long #define pi acos(-1) using namespace std; const int N = 1e5+10; const int MOD = 1e9+7; signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); string s; int cn=0; while(cin>>s) { for(int i=0;i<=s.size()-1;i++) { if(s[i]==':'&&s[i+1]=='w') { cn++; } } } cout<<cn<<endl; return 0; }
荷香竟深湎，永待盛夏陌。
dfs维护路径(我这里是把路径维护成一个字符串了)
#include<iostream> #include<algorithm> #include<map> #include<algorithm> #include<utility> #include<vector> #include<queue> #define PII pair<string,string> #define rep(i,a,b) for(int i=a;i<=b;i++) #define int long long #define pi acos(-1) using namespace std; const int N = 10; const int MOD = 1e9+7; bool f; void dfs(int a,int b,int c,int d,string s) { if(f||s.size()>16) return ; a%=5;b%=5;c%=5;d%=5; if(a==b&&b==c&&c==d) { cout<<s.size()<<endl; for(int i=0;i<s.size();i++) cout<<s[i]<<" "; if(s.size()) cout<<endl; f=true; return ; } dfs(a+1,b+1,c,d+1,s+"1"); dfs(a+1,b+1,c+1,d,s+"2"); dfs(a,b+1,c+1,d+1,s+"3"); dfs(a+1,b,c+1,d+1,s+"4"); } int a[4]; signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin>>T; while(T--) { f=false; cin>>a[0]>>a[1]>>a[2]>>a[3]; dfs(a[0],a[1],a[2],a[3],""); } return 0; }
相思子肯来，约在莲花岸。
1e3 * 1e3暴力扫就行
#include<iostream> #include<algorithm> #include<map> #include<algorithm> #include<utility> #include<vector> #define PII pair<int,int> #define rep(i,a,b) for(int i=a;i<=b;i++) #define int long long #define pi acos(-1) using namespace std; const int N = 10; const int MOD = 1e9+7; //8行 7列 int x[N],y[N],k[N]; int ex[N],ey[N],ek[N]; int dist(int i,int j) { return (x[i]-ex[j])*(x[i]-ex[j]) + (y[i]-ey[j])*(y[i]-ey[j]); } signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; rep(i,1,n) cin>>x[i]>>y[i]>>k[i]; rep(i,1,m) cin>>ex[i]>>ey[i]>>ek[i]; rep(i,1,n) { int mx=0; int mi=0x3f3f3f3f; int po; rep(j,1,m) { int d = dist(i,j); if(k[i]==1) { if(d>mx) { mx=d; po=j; } }else { if(d<mi) { mi=d; po=j; } } } cout<<po<<" "; } cout<<endl; rep(i,1,m) { int mx=0; int mi=0x3f3f3f3f; int po; rep(j,1,n) { int d = dist(j,i); if(ek[i]==1) { if(d>mx) { mx=d; po=j; } }else { if(d<mi) { mi=d; po=j; } } } cout<<po<<" "; } cout<<endl; return 0; }
潇潇日暮时，掠水鸳鸯散。
01 背包
#include<iostream> #include<algorithm> #include<map> #include<algorithm> #include<utility> #include<vector> #define PII pair<int,int> #define rep(i,a,b) for(int i=a;i<=b;i++) #define int long long #define pi acos(-1) using namespace std; const int N = 1e5+10; const int MOD = 1e9+7; int a[N],b[N],dp[N]; signed main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n,m; cin>>n>>m; rep(i,1,m) cin>>a[i]>>b[i]; for(int i=1;i<=m;i++) { for(int j=n;j>=a[i];j--) { dp[j]=max(dp[j],dp[j-a[i]]+b[i]); } } cout<<dp[n]<<endl; return 0; }
