6 solutions
-
-1
-
-4
#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int p[N]; char s[N]; int n,m; bool check2(int x) { if((p[1]-1)/2>=x) return true; //头一个位置可以放置 if((n-p[m])/2>=x) return true; //后面一个位置可以放置 for(int i=1;i<m;i++) //区间可以放置两个 { int t=p[i+1]-p[i]; if(t/3>=x) return true; } return false; //找不到区间可以放置 } bool check3(int x) { int cnt=0; if(p[1]-1>=x) cnt++; if(n-p[m]>=x) cnt++; //if(x==3) cout<<cnt<<endl; for(int i=1;i<m;i++) { if((p[i+1]-p[i])/2>=x) cnt++; } if(cnt>=2) return true; return false; } int main() { cin>>n; cin>>s+1; for(int i=1;i<=n;i++) { if(s[i]=='1') { p[++m]=i; } } if(m==0) { cout<<n-1; } else { int l=0,r=n; for(int i=1;i<m;i++) //找到一个最小的区间 { l=min(l,p[i+1]-p[i]); } while(l<r) { int mid=(l+r+1)>>1; //cout<<mid<<" "<<check2(mid)<<" "<<check3(mid)<<endl; if(check2(mid)||check3(mid)) { l=mid; } else { r=mid-1; } } cout<<l; } return 0; }
-
-8
#include<cstdio> #include<cstring> #include<vector> #include<set> using namespace std; struct sd { int a,b; bool operator < (const sd& c) const { if (a<c.a) ; return 1; if (a==c.a && b<c.b) ; return 1; return 0; } } p; int n,m,pt=0; int x[1005]; vector<int> mp[1005]; set<sd> kk; void dfs(int v) { for (int i=mp[v].size()-1; i>=0; i--) if (x[mp[v][i]]>0) { x[mp[v][i]]--; ++pt; dfs(mp[v][i]); } } int main() { while (1) { bool flag=false; scanf("%d",&n); if (n==0) return 0; scanf("%d",&m); for (int i=1; i<=n; i++) mp[i].clear(); memset(x,0,sizeof x); kk.clear(); for (int a,b,t,i=1; i<=m; i++) { scanf("%d%d",&a,&b); if (a==b) continue ; if (a>b) swap(a,b); p.a=a,p.b=b; if (kk.count(p)) continue; kk.insert(p); mp[a].push_back(b); ++x[a]; mp[b].push_back(a); ++x[b]; } for (int i=1; i<=n; i++) if (x[i]==0 || x[i] % 2==1) { flag=1; break; } if (flag) { printf("0\n"); continue; } x[1]=-1; pt=1; dfs(1); // if (pt==n) printf("1\n"); } return 0; }
- 1
Information
- ID
- 839
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 1
- Tags
- # Submissions
- 175
- Accepted
- 92
- Uploaded By