枚举题意，五十分钟看懂题，十分钟过三道，tarjan还写挂了，大型翻车现场。
A、你有n卢布，要把卢布换成美元和欧元，一美元和一欧元对应的卢布数是给定的
美元有几种面值：1、2、5、10、20、50、100
欧元有几种面值：5、10、20、50、100、200
你可以兑换任意数量的欧元和美元，但你兑换的美元和欧元必须可以用上面的纸币表示出来，问你最后手里最少剩下多少卢布
美元只要能换就换，因为1美元可以表示任何数字，欧元只能5欧5欧地换，枚举一下换成美元的张数即可
代码：
#include <bits/stdc++.h> #define int long long #define sc(a) scanf("%lld",&a) #define scc(a,b) scanf("%lld %lld",&a,&b) #define sccc(a,b,c) scanf("%lld %lld %lld",&a,&b,&c) #define schar(a) scanf("%c",&a) #define pr(a) printf("%lld",a) #define fo(i,a,b) for(int i=a;i<b;++i) #define re(i,a,b) for(int i=a;i<=b;++i) #define rfo(i,a,b) for(int i=a;i>b;--i) #define rre(i,a,b) for(int i=a;i>=b;--i) #define prn() printf("\n") #define prs() printf(" ") #define mkp make_pair #define pii pair<int,int> #define pub(a) push_back(a) #define pob() pop_back() #define puf(a) push_front(a) #define pof() pop_front() #define fst first #define snd second #define frt front() #define bak back() #define mem0(a) memset(a,0,sizeof(a)) #define memmx(a) memset(a,0x3f3f,sizeof(a)) #define memmn(a) memset(a,-0x3f3f,sizeof(a)) #define debug #define db double #define yyes cout<<"YES"<<endl; #define nno cout<<"NO"<<endl; using namespace std; typedef vector<int> vei; typedef vector<pii> vep; typedef map<int,int> mpii; typedef map<char,int> mpci; typedef map<string,int> mpsi; typedef deque<int> deqi; typedef deque<char> deqc; typedef priority_queue<int> mxpq; typedef priority_queue<int,vector<int>,greater<int> > mnpq; typedef priority_queue<pii> mxpqii; typedef priority_queue<pii,vector<pii>,greater<pii> > mnpqii; const int maxn=500005; const int inf=0x3f3f3f3f3f3f3f3f; const int MOD=100000007; const db eps=1e-10; int qpow(int a,int b){int tmp=a%MOD,ans=1;while(b){if(b&1){ans*=tmp,ans%=MOD;}tmp*=tmp,tmp%=MOD,b>>=1;}return ans;} int lowbit(int x){return x&-x;} int max(int a,int b){return a>b?a:b;} int min(int a,int b){return a<b?a:b;} int mmax(int a,int b,int c){return max(a,max(b,c));} int mmin(int a,int b,int c){return min(a,min(b,c));} void mod(int &a){a+=MOD;a%=MOD;} bool chk(int now){} int half(int l,int r){while(l<=r){int m=(l+r)/2;if(chk(m))r=m-1;else l=m+1;}return l;} int ll(int p){return p<<1;} int rr(int p){return p<<1|1;} int mm(int l,int r){return (l+r)/2;} int lg(int x){if(x==0) return 1;return (int)log2(x)+1;} bool smleql(db a,db b){if(a<b||fabs(a-b)<=eps)return true;return false;} db len(db a,db b,db c,db d){return sqrt((a-c)*(a-c)+(b-d)*(b-d));} bool isp(int x){if(x==1)return false;if(x==2)return true;for(int i=2;i*i<=x;++i)if(x%i==0)return false;return true;} int n,d,e; int ans=inf; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>d>>e; int k=0; while(1){ if(k*d>n) break; int tmp=n; tmp-=k*d; int ou=tmp/e; ou-=ou%5; tmp-=ou*e; ans=min(ans,tmp); k++; } cout<<ans; return 0; }
B、b个男孩和g个女孩吃饭，一共来n个人，现在有n+1张桌子，第i张桌子可以坐i个男生和n-i个女生
问你最少需要多少张桌子才能使得不管来几个男生女生都能坐
SB题意，看半天没搞懂，两边扫一下就完事了，分别表示男生全来和女生全来的情况
代码：
#include <bits/stdc++.h> #define int long long #define sc(a) scanf("%lld",&a) #define scc(a,b) scanf("%lld %lld",&a,&b) #define sccc(a,b,c) scanf("%lld %lld %lld",&a,&b,&c) #define schar(a) scanf("%c",&a) #define pr(a) printf("%lld",a) #define fo(i,a,b) for(int i=a;i<b;++i) #define re(i,a,b) for(int i=a;i<=b;++i) #define rfo(i,a,b) for(int i=a;i>b;--i) #define rre(i,a,b) for(int i=a;i>=b;--i) #define prn() printf("\n") #define prs() printf(" ") #define mkp make_pair #define pii pair<int,int> #define pub(a) push_back(a) #define pob() pop_back() #define puf(a) push_front(a) #define pof() pop_front() #define fst first #define snd second #define frt front() #define bak back() #define mem0(a) memset(a,0,sizeof(a)) #define memmx(a) memset(a,0x3f3f,sizeof(a)) #define memmn(a) memset(a,-0x3f3f,sizeof(a)) #define debug #define db double #define yyes cout<<"YES"<<endl; #define nno cout<<"NO"<<endl; using namespace std; typedef vector<int> vei; typedef vector<pii> vep; typedef map<int,int> mpii; typedef map<char,int> mpci; typedef map<string,int> mpsi; typedef deque<int> deqi; typedef deque<char> deqc; typedef priority_queue<int> mxpq; typedef priority_queue<int,vector<int>,greater<int> > mnpq; typedef priority_queue<pii> mxpqii; typedef priority_queue<pii,vector<pii>,greater<pii> > mnpqii; const int maxn=500005; const int inf=0x3f3f3f3f3f3f3f3f; const int MOD=100000007; const db eps=1e-10; int qpow(int a,int b){int tmp=a%MOD,ans=1;while(b){if(b&1){ans*=tmp,ans%=MOD;}tmp*=tmp,tmp%=MOD,b>>=1;}return ans;} int lowbit(int x){return x&-x;} int max(int a,int b){return a>b?a:b;} int min(int a,int b){return a<b?a:b;} int mmax(int a,int b,int c){return max(a,max(b,c));} int mmin(int a,int b,int c){return min(a,min(b,c));} void mod(int &a){a+=MOD;a%=MOD;} bool chk(int now){} int half(int l,int r){while(l<=r){int m=(l+r)/2;if(chk(m))r=m-1;else l=m+1;}return l;} int ll(int p){return p<<1;} int rr(int p){return p<<1|1;} int mm(int l,int r){return (l+r)/2;} int lg(int x){if(x==0) return 1;return (int)log2(x)+1;} bool smleql(db a,db b){if(a<b||fabs(a-b)<=eps)return true;return false;} db len(db a,db b,db c,db d){return sqrt((a-c)*(a-c)+(b-d)*(b-d));} bool isp(int x){if(x==1)return false;if(x==2)return true;for(int i=2;i*i<=x;++i)if(x%i==0)return false;return true;} int b,g,n; int bb[maxn],gg[maxn]; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>b>>g>>n; re(i,0,n) bb[i]=i,gg[i]=n-i; int x=min(n,b); int y=n-x; int l; re(i,0,n) if(bb[i]==x&&gg[i]==y) {l=i;break;} y=min(n,g); x=n-y; int r; re(i,0,n) if(bb[i]==x&&gg[i]==y) {r=i;break;} cout<<abs(r-l)+1; return 0; }
C、给你一堆括号序列，问你能否通过交换一堆括号使得其编程有序，也可以不交换
上个栈，最后栈里只剩下一个左括号并且过程中有一个右括号未匹配就YES，直接匹配也输出YES，否则NO
代码：
#include <bits/stdc++.h> #define int long long #define sc(a) scanf("%lld",&a) #define scc(a,b) scanf("%lld %lld",&a,&b) #define sccc(a,b,c) scanf("%lld %lld %lld",&a,&b,&c) #define schar(a) scanf("%c",&a) #define pr(a) printf("%lld",a) #define fo(i,a,b) for(int i=a;i<b;++i) #define re(i,a,b) for(int i=a;i<=b;++i) #define rfo(i,a,b) for(int i=a;i>b;--i) #define rre(i,a,b) for(int i=a;i>=b;--i) #define prn() printf("\n") #define prs() printf(" ") #define mkp make_pair #define pii pair<int,int> #define pub(a) push_back(a) #define pob() pop_back() #define puf(a) push_front(a) #define pof() pop_front() #define fst first #define snd second #define frt front() #define bak back() #define mem0(a) memset(a,0,sizeof(a)) #define memmx(a) memset(a,0x3f3f,sizeof(a)) #define memmn(a) memset(a,-0x3f3f,sizeof(a)) #define debug #define db double #define yyes cout<<"YES"<<endl; #define nno cout<<"NO"<<endl; using namespace std; typedef vector<int> vei; typedef vector<pii> vep; typedef map<int,int> mpii; typedef map<char,int> mpci; typedef map<string,int> mpsi; typedef deque<int> deqi; typedef deque<char> deqc; typedef priority_queue<int> mxpq; typedef priority_queue<int,vector<int>,greater<int> > mnpq; typedef priority_queue<pii> mxpqii; typedef priority_queue<pii,vector<pii>,greater<pii> > mnpqii; const int maxn=500005; const int inf=0x3f3f3f3f3f3f3f3f; const int MOD=100000007; const db eps=1e-10; int qpow(int a,int b){int tmp=a%MOD,ans=1;while(b){if(b&1){ans*=tmp,ans%=MOD;}tmp*=tmp,tmp%=MOD,b>>=1;}return ans;} int lowbit(int x){return x&-x;} int max(int a,int b){return a>b?a:b;} int min(int a,int b){return a<b?a:b;} int mmax(int a,int b,int c){return max(a,max(b,c));} int mmin(int a,int b,int c){return min(a,min(b,c));} void mod(int &a){a+=MOD;a%=MOD;} bool chk(int now){} int half(int l,int r){while(l<=r){int m=(l+r)/2;if(chk(m))r=m-1;else l=m+1;}return l;} int ll(int p){return p<<1;} int rr(int p){return p<<1|1;} int mm(int l,int r){return (l+r)/2;} int lg(int x){if(x==0) return 1;return (int)log2(x)+1;} bool smleql(db a,db b){if(a<b||fabs(a-b)<=eps)return true;return false;} db len(db a,db b,db c,db d){return sqrt((a-c)*(a-c)+(b-d)*(b-d));} bool isp(int x){if(x==1)return false;if(x==2)return true;for(int i=2;i*i<=x;++i)if(x%i==0)return false;return true;} int n; string s; stack<char> st; int l=0; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>s; fo(i,0,n){ if(s[i]=='('){ st.push('('); } else{ if(st.empty()) l++; else st.pop(); } } if((l==0&&st.empty())||(l==1&&st.size()==1)) cout<<"Yes"<<endl; else cout<<"No"<<endl; return 0; }
D、看到standing里面很多写dp的，完全看不懂……
一开始大爆搜，搜出所有可能路径，路径上每个点加一，如果有一个点每条路径都经过，那么输出1
比赛时rhy糊了个算法，把所有可以到达终点的路径打上标记，对这些标记建立四联通的无向图，跑一遍tarjan
不能到达答案为0，如果有割点，答案为1，否则为2
tarjan要注意一个问题，起点不能做为割点
打标记也要注意一个问题，只有抵达终点的路径才打标记，否则会错误判断割点。
这种样例就会出锅：
4 4
....
....
.#..
.#..
左下角虽然有个割点，但是完全起不到作用。此外dfs的时候还得注意或运算短路的性质，免得搜完向下的路径就不搜向右的路径了。
代码：
#include <bits/stdc++.h> #define int long long #define sc(a) scanf("%lld",&a) #define scc(a,b) scanf("%lld %lld",&a,&b) #define sccc(a,b,c) scanf("%lld %lld %lld",&a,&b,&c) #define schar(a) scanf("%c",&a) #define pr(a) printf("%lld",a) #define fo(i,a,b) for(int i=a;i<b;++i) #define re(i,a,b) for(int i=a;i<=b;++i) #define rfo(i,a,b) for(int i=a;i>b;--i) #define rre(i,a,b) for(int i=a;i>=b;--i) #define prn() printf("\n") #define prs() printf(" ") #define mkp make_pair #define pii pair<int,int> #define pub(a) push_back(a) #define pob() pop_back() #define puf(a) push_front(a) #define pof() pop_front() #define fst first #define snd second #define frt front() #define bak back() #define mem0(a) memset(a,0,sizeof(a)) #define memmx(a) memset(a,0x3f3f,sizeof(a)) #define memmn(a) memset(a,-0x3f3f,sizeof(a)) #define debug #define db double #define yyes cout<<"YES"<<endl; #define nno cout<<"NO"<<endl; using namespace std; typedef vector<int> vei; typedef vector<pii> vep; typedef map<int,int> mpii; typedef map<char,int> mpci; typedef map<string,int> mpsi; typedef deque<int> deqi; typedef deque<char> deqc; typedef priority_queue<int> mxpq; typedef priority_queue<int,vector<int>,greater<int> > mnpq; typedef priority_queue<pii> mxpqii; typedef priority_queue<pii,vector<pii>,greater<pii> > mnpqii; const int maxn=1000005; const int inf=0x3f3f3f3f3f3f3f3f; const int MOD=100000007; const db eps=1e-10; int qpow(int a,int b){int tmp=a%MOD,ans=1;while(b){if(b&1){ans*=tmp,ans%=MOD;}tmp*=tmp,tmp%=MOD,b>>=1;}return ans;} int lowbit(int x){return x&-x;} int max(int a,int b){return a>b?a:b;} int min(int a,int b){return a<b?a:b;} int mmax(int a,int b,int c){return max(a,max(b,c));} int mmin(int a,int b,int c){return min(a,min(b,c));} void mod(int &a){a+=MOD;a%=MOD;} bool chk(int now){} int half(int l,int r){while(l<=r){int m=(l+r)/2;if(chk(m))r=m-1;else l=m+1;}return l;} int ll(int p){return p<<1;} int rr(int p){return p<<1|1;} int mm(int l,int r){return (l+r)/2;} int lg(int x){if(x==0) return 1;return (int)log2(x)+1;} bool smleql(db a,db b){if(a<b||fabs(a-b)<=eps)return true;return false;} db len(db a,db b,db c,db d){return sqrt((a-c)*(a-c)+(b-d)*(b-d));} bool isp(int x){if(x==1)return false;if(x==2)return true;for(int i=2;i*i<=x;++i)if(x%i==0)return false;return true;} int n,m,timer=0,cut=0; bool can=0; char rhy[maxn]; vector<char> s[maxn]; vei dfn[maxn],low[maxn]; int a[4]={1,0,-1,0}; int b[4]={0,1,0,-1}; bool ok(int i,int j){ if(i<0||i>=n||j<0||j>=m) return 0; if(s[i][j]=='#') return 0; return 1; } bool dfs(int i,int j){ if(i<0||i>=n||j<0||j>=m) return 0; if(s[i][j]=='#') return 0; if(s[i][j]=='0') return 1; if(i==n-1&&j==m-1){ can=1; s[i][j]='0'; return 1; } bool now=0; now|=dfs(i+1,j); now|=dfs(i,j+1); if(now){ // cout<<i<<' '<<j<<endl; s[i][j]='0'; if(ok(i+1,j)) s[i+1][j]='0'; if(ok(i,j+1)) s[i][j+1]='0'; return 1; } else {s[i][j]='#';return 0;} } void tarjan(int x,int y){ dfn[x][y]=low[x][y]=++timer; fo(i,0,4){ int dx=x+a[i],dy=y+b[i]; if(dx<0||dx>=n||dy<0||dy>=m||s[dx][dy]!='0') continue; if(!dfn[dx][dy]){ tarjan(dx,dy); low[x][y]=min(low[x][y],low[dx][dy]); if(low[dx][dy]>=dfn[x][y] &&(x!=0||y!=0)){ // cout<<x<<' '<<y<<endl; cut++; } } else{ low[x][y]=min(low[x][y],dfn[dx][dy]); } } } signed main(){ scc(n,m); fo(i,0,n){ scanf("%s",rhy); fo(j,0,m) dfn[i].pub(0),low[i].pub(0),s[i].pub(rhy[j]); } dfs(0,0); s[0][0]=s[n-1][m-1]='0'; // fo(i,0,n) fo(j,0,m) cout<<s[i][j]<<(j==m-1?'\n':' '); if(!can) cout<<0; else{ tarjan(0,0); if(!cut) cout<<2; else cout<<1; } return 0; } /* 2 4 .... ..#. 3 3 .#. #.. ... 4 4 .... .... .#.. .#.. */