codeforces網站，Codeforces Round 496

感謝上天讓我碰到了div 3

#include <bits/stdc++.h>
using namespace std;
#define LOCAL freopen("in","r",stdin);\freopen("out","w",stdout);
#define DBG2(x,y) cout<<(#x)<<"\t"<<x<<(#y)<<"\t"<<y<<endl;
int n,t,fnum,ts;
vector<int> v;int main()
{LOCALcin>>n;for(int i=1;i<=n;i++){    cin>>t;if((t==fnum)&&(t==1)) v.push_back(fnum);if(t<fnum) v.push_back(fnum);fnum = t;}v.push_back(fnum);cout<<v.size()<<endl;for(int i=0;i<v.size();i++)cout<<v[i]<< " ";}

#include<bits/stdc++.h>
using namespace std;
#define LOACL  freopen("in","r",stdin);\freopen("out","w",stdout); int main()
{LOACLstring a,b;cin>>a>>b;int lena = a.length() ,lenb = b.length();int s=0;for(int i=lena-1,j=lenb-1;i>=0&&j>=0;i--,j--){if(a[i]==b[j]) s++;else break;}cout<<lena+lenb-2*s<<endl;
} 

#include<bits/stdc++.h>
using namespace std;
#define LOACL  freopen("in","r",stdin);\freopen("out","w",stdout);  
#define DBG(x) cout<<(#x)<<"="<<x<<endl
#define DBG2(x,y) cout<<(#x)<<"="<<x<<"\t"<<(#y)<<"="<<y<<endl
#define DBG3(x,y,z) cout<<(#x)<<"="<<x<<"\t"<<(#y)<<"="<<y<<"\t"<<(#z)<<"="<<z<<endlint main()
{LOACL int n,t,num=0;map<int,int> m ;cin>>n;for(int i=0;i<n;i++){ cin>>t;m[t]++;}map<int,int>::iterator it  = m.begin();for(;it!=m.end();it++){if((*it).second==0)continue;bool flag = false;for(int j=0;j<=31;j++){int s = 1<<j;int k = (*it).first;if(k>s) continue; if(s-k == k && m[k]>=2){//    DBG3(s,k,"a");flag = true;break;}else if(s-k!=k&& m[s-k]>0){//    DBG3(s,k,"b");flag = true;break;}}if(!flag) num+=(*it).second;//DBG3((*it).first,flag,num);
        }cout<<num<<endl;}

#include<bits/stdc++.h>
using namespace std;
#define LOACL  freopen("in","r",stdin);\freopen("out","w",stdout); #define DBG(x) cout<<(#x)<<"="<<x<<endl
#define DBG2(x,y) cout<<(#x)<<"="<<x<<"\t"<<(#y)<<"="<<y<<endl
#define DBG3(x,y,z) cout<<(#x)<<"="<<x<<"\t"<<(#y)<<"="<<y<<"\t"<<(#z)<<"="<<z<<endlint main()
{LOACLstring str;cin>>str;int bnum=0,num=0;vector<int> v;for(int i=str.length()-1;i>=0;i--){int tmp = str[i]-'0';if(tmp%3==0){//DBG(tmp);num++;v.clear();//    cout<<v.size();
        }else {bool flag = false;int v_size = v.size();for(int i=0;i<v_size;i++){int k = tmp*10+v[i];if(k%3==0){//    DBG(k);num++;v.clear();flag =  true;break;}else{v[i] = k;}}if(flag) continue;v.push_back(tmp);}}cout<<num<<endl;
}

E 題目，感謝Q神的思路 ，維護一個游標，處理好區間位數為m 和區間中位數為m-1 做差值。

#include<bits/stdc++.h>
using namespace std;
#define LOACL  freopen("in","r",stdin);\freopen("out","w",stdout); #define DBG(x) cout<<(#x)<<"="<<x<<endl
#define DBG2(x,y) cout<<(#x)<<"="<<x<<"\t"<<(#y)<<"="<<y<<endl
#define DBG3(x,y,z) cout<<(#x)<<"="<<x<<"\t"<<(#y)<<"="<<y<<"\t"<<(#z)<<"="<<z<<endlconst int sz = (int)2e5+10;
typedef long long ll;
ll c[sz*2],a[sz],b[sz],n,m,cur,sum,i,j ;
ll ss(int m ,ll res = 0)
{#if 1 sum = 0; cur = n+1; memset(c,0,sizeof(c)); c[cur] =1;for(int i  =1 ;i<=n;i++){if(a[i]<=m) sum+=c[++cur];else sum-=c[cur--];res+=sum;c[cur]++; }return res;#endif}
int main()
{LOACLcin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];cout<<ss(m)-ss(m-1)<<endl;    
}

#include<bits/stdc++.h>
using namespace std;
#define LOACL  freopen("in","r",stdin);\freopen("out","w",stdout); 
const int sz = (int)2e5+10; 
int n,m,k,u,v,dist[sz];
string res;
vector<string> ans;
vector<int> g[sz],num[sz],ids[sz];void bfs()
{memset(dist,-1,sizeof(dist));queue<int> q;q.push(1);dist[1]=0;while(!q.empty()){int v = q.front();q.pop();int n_size = g[v].size();for(int i=0;i<n_size;i++){int to  = g[v][i];if(dist[to]==-1){dist[to] = dist[v]+1;q.push(to);}if(dist[to]==dist[v]+1){ids[to].push_back(num[v][i]);}}}
}
void write()
{cout<<ans.size()<<endl;for(int i=0;i<ans.size();i++){cout<<ans[i].c_str()<<endl;}exit(0);
}
void rec(int v)
{if(v==n+1){ans.push_back(res);if(ans.size()==k)write();return ;}int ids_size = ids[v].size();for(int i=0;i<ids_size;i++){    int id = ids[v][i];res[id]='1';rec(v+1);res[id]='0';}
}
int main()
{LOACLcin>>n>>m>>k;for(int i=0;i<m;i++){cin>>u>>v;g[u].push_back(v);g[v].push_back(u);num[u].push_back(i);num[v].push_back(i); res+='0';}bfs();rec(2);write(); 
}

codeforces網站。?