http://codeforces.com/contest/938
A:sb题
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=100000+10,maxn=2000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; bool ok(char s) { if(s=='a'||s=='e'||s=='i'||s=='o'||s=='u'||s=='y')return 1; return 0; } int main() { fio; string s; int n; cin>>n>>s; while(1) { // cout<<s<<endl; bool f=1; for(int i=1;i<s.size();i++) { if(ok(s[i])&&ok(s[i-1])) { f=0; s=s.substr(0,i)+s.substr(i+1,s.size()); break; } } if(f)break; } cout<<s<<" "; return 0; } /******************** ********************/
B:sb题
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=100000+10,maxn=2000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; int a[N]; int main() { int n,ans=-1; scanf("%d",&n); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); ans=max(ans,min(x-1,1000000-x)); } printf("%d ",ans); return 0; } /******************** ********************/
import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.StringTokenizer; import java.io.IOException; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.InputStream; import java.math.*; public class Main { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); PrintWriter out = new PrintWriter(outputStream); TaskD solver = new TaskD(); solver.solve(1, in, out); out.close(); } static class TaskD { static final int MAX_COORD = (int) 1e5 + 10; static final int INF = (int) 1e9; public void solve(int testNumber, InputReader in, PrintWriter out) { int n=in.nextInt(),ans=-1; for(int i=1;i<=n;i++) { int x=in.nextInt(); ans=Math.max(ans,Math.min(x-1,1000000-x)); } out.println(ans); } } static class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } } }
n=int(input()) x=input().split(' ') ans=-1 for i in x: ans=max(ans,min(int(i)-1,1000000-int(i))) print(ans)
C:m-free代表所有n*n的m*m子矩阵至少含一个0,给你x,要求找一组n,m中 的1的个数最多且为x
解法:推公式,nm中最多1为n*n-(n/m)*(n/m),预处理平方,然后二分求n,m
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=100000+10,maxn=2000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; map<ll,ll>m; void init() { for(ll i=1;i<=40000;i++) m[i*i]=i; } int main() { init(); int t; scanf("%d",&t); while(t--) { ll x,f=0; scanf("%lld",&x); for(ll i=1;i<=40000;i++) { ll te=m[x+i*i]; if(te) { ll ans=te/i; if(te*te-(int)(te/ans)*(te/ans)==x) { f=1; printf("%lld %lld ",te,ans); break; } } } if(!f)puts("-1"); } return 0; } /******************** ********************/
D:找每个点到另一个点的最小价值,价值是边权值和*2加所到点的权值;
解法:加一个超级源,该点到每一个点的权值为点的权值,然后该点到每一个最短路就是每个点的答案了,(会卡spfa)
ps:再也不写spfa了,dij很好写啊,spfa复杂度就是个玄学
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=200000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; struct edge{ int to,Next; ll c; }e[maxn]; int cnt,head[N]; void init() { cnt=0; memset(head,-1,sizeof head); } void add(int u,int v,ll w) { e[cnt].to=v; e[cnt].c=w; e[cnt].Next=head[u]; head[u]=cnt++; } priority_queue<pii,vector<pii>,greater<pii> >q; ll dis[N]; void dij(int s) { for(int i=0;i<N;i++) dis[i]=1e18; dis[s]=0; q.push(mp(0,s)); while(!q.empty()) { pii u=q.top(); q.pop(); int x=u.se; if(dis[x]<u.fi)continue; for(int i=head[x];~i;i=e[i].Next) { int To=e[i].to; if(dis[To]>dis[x]+e[i].c) { dis[To]=dis[x]+e[i].c; q.push({dis[To],To}); } } } } int main() { int n,m; scanf("%d%d",&n,&m); init(); for(int i=0;i<m;i++) { int a,b; ll w; scanf("%d%d%lld",&a,&b,&w); add(a,b,2*w); add(b,a,2*w); } for(int i=1;i<=n;i++) { ll w; scanf("%lld",&w); add(i,n+1,w); add(n+1,i,w); } dij(n+1); for(int i=1;i<=n;i++) printf("%lld ",dis[i]); puts(""); return 0; } /******************** ********************/
E:给你n个数求每个排列的价值总和,对于一个排列来说价值就是从1到n,依次找比上一个访问过的点权值大的那个点的价值加起来
解法:明显的排列组合,我们分别算每个数的贡献,假设现在有一个数x,比它小的数有a个,比它大的数有b个,那么x前面没有比x大 的排列情况一共有多少个呢?
答案是b!*(b+1)*...*(b+a+1),因为先把b个数全排列是b!,然后用插空法,依次插入比x小的数空的个数依次是b+1...b+a+1
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=2000000+10,maxn=1000000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; ll f[N],a[maxn]; void init() { f[0]=1; for(ll i=1;i<N;i++) f[i]=f[i-1]*i%mod; } ll quick(ll a,ll b) { ll ans=1; while(b) { if(b&1)ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } int main() { init(); int n; scanf("%d",&n); for(int i=0;i<n;i++)scanf("%lld",&a[i]); sort(a,a+n); ll ans=0; for(int i=0;i<n;i++) { ll pre=lower_bound(a,a+n,a[i])-a; ll suf=n-pre-1; if(a[i]==a[n-1])continue; // printf("%lld %lld %lld ",pre,suf,solve(pre,suf)); ans=(ans+f[n]*quick(suf+1,mod-2)%mod*a[i])%mod; } printf("%lld ",ans); return 0; } /******************** ********************/
F:有一个字符串,要求删除logn向下取整次,每次删除长度为2*(i-1)的字符串,求删除后字典序最小的字符串
解法:可以考虑,用string的二维dp,dp[i][j]代表前i为,删除为j状态的最小字符串,枚举i复杂度O(n),枚举状态复杂度O(nlogn),字符串操作复杂度O(n),然后复杂度是O(n^3logn),明显会爆炸,所以改变一下,我们只用dp[i][j]来表示当前位置是不是最小的情况,只用开bool型即可,每次更新时,贪心的只从最小情况来转移,然后求出下一层的最小情况,复杂度就降到了O(n^2logn),还可以用滚动数组,只开成dp[2][n]来降低空间复杂度
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("unroll-loops") #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define C 0.5772156649 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #define pil pair<int,ll> #define pii pair<int,int> #define ull unsigned long long #define base 1000000000000000000 #define fio ios::sync_with_stdio(false);cin.tie(0) using namespace std; const double g=10.0,eps=1e-12; const int N=5000+10,maxn=1200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f; bool dp[2][N]; string s; int main() { fio; cin>>s; int n=s.size(),k=0; while((1<<(k+1)<=n))k++; int pos=n-(1<<k)+1,now=0,pre=1; dp[now][0]=1; for(int i=0;i<pos;i++) { for(int j=0;j<(1<<k);j++) { if(!dp[now][j])continue; for(int u=0;u<k;u++) if(!((j>>u)&1)) dp[now][j^(1<<u)]=1; } char mi='z'; for(int j=0;j<(1<<k);j++) if(dp[now][j]) mi=min(mi,s[i+j]); putchar(mi); memset(dp[pre],0,sizeof dp[pre]); for(int j=0;j<(1<<k);j++) if(dp[now][j]&&s[i+j]==mi) dp[pre][j]=1; swap(now,pre); } return 0; } /******************** ********************/
G:待补