A | B | C | D | E | F | G | H | I | J | K | L | M | 总题数 | 通过题数 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
! | ! | O | O | ! | O | 12 | 3 | |||||||
Ø | Ø | O | Ø | Ø | O | Ø | O | 12 | ? |
证明见《离散数学》鸽巢原理
思想是分成\(\sqrt (n)\)个长度不超过\(\sqrt (n)\)的单增子序列,每个子序列按第一位数,从大到小排列
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,T; int main(){ cin>>T; while(T--){ cin>>n; int cnt=1; while(cnt*cnt<n)cnt++; for(int i=cnt;i>=1;i--) for(int j=i;j<=n;j+=cnt) printf("%d ",j); puts(""); } return 0; }
题意是求一个大系数二元二次函数的最小值(保证最小值存在)。
最值的求法只需用到两次二次函数最值,(每次削减一个变量)
若按此法,求解时会炸long double的精度,需要用__float128
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define int long long __float128 A,B,C,D,E,F; const int maxn=1e5+1000; int n; int a[maxn]; inline void read(int &x){ x=0;int fl=1;char tmp=getchar(); while(tmp<'0'||tmp>'9')fl=tmp=='-'?-fl:fl,tmp=getchar(); while(tmp>='0'&&tmp<='9')x=(x<<1)+(x<<3)+tmp-'0',tmp=getchar(); x=x*fl; } signed main(){ // freopen("std.txt","r",stdin); int T;cin>>T; while(T--){ cin>>n; for(int i=1;i<=n;i++) read(a[i]); A=B=C=D=E=F=0; for(int i=1;i<=n;i++){ A+=i*i,C+=2*i,D+=-2*i*a[i],E+=-2*a[i],F+=a[i]*a[i]; } B=n; __float128 x,y,z; x=(-C/A*C/4+B),y=-C/A*D/2+E,z=F-D/A*D/4; long double ans=z-y/x*y/4; printf("%.12Lf\n",ans); } return 0; }
为了防止精度爆炸,也可以直接用最小二乘法求线性回归(大概是出题思路)
LD sx = 0, sxx = 0, sy = 0, sxy = 0; loop(i, 1, n) { sx += i; sxx += (LD)i * i; sy += a[i]; sxy += (LD)i * a[i]; } LD bb = (n * sxy - sx * sy) / (n * sxx - sx * sx); LD aa = (sxx * sy - sx * sxy) / (n * sxx - sx * sx); LD res = 0; loop(i, 1, n) { LD d = a[i] - (bb * i + aa); res += d*d; } printf("%.8Lf\n", res);
这题是队友做的,滚动数组优化空间
给一个初始括号串,和最终合法括号串的长度。问合法括号串的个数。
接受\(O(n^3)\)的复杂度
比赛时没仔细算复杂度,以为\(O(n^3)\)不可做。另外受到上次杭电比赛的影响,以为是区间dp。
仍需加强对dp的练习。
不考虑和初始括号串的lcs。那么合法括号串个数可以用g(i,j)数组来求,i->确定括号串的位数,j->左括号比右括号多的个数(右比左多则非法)
定义f(i,j,k)表示,确定合法串的前i位,左比右多k个,lcs至少为j位的状态的个数。
#include<bits/stdc++.h> #define int unsigned int using namespace std; const int maxn=201; const int mod=1e9+7; int n,m; int f[maxn][maxn][maxn]; char s[maxn]; signed main(){ int T;cin>>T; while(T--){ memset(f,0,sizeof f); f[0][0][0]=1; cin>>m>>n; scanf("%s",s+1); for(int i=1;i<=n;i++){ for(int j=0;j<=i&&j<=m;j++) for(int k=0;k<=i;k++){ printf("(%d,%d,%d): ",i,j,k); if(k){ if(j&&s[j]=='(')f[i][j][k]=f[i-1][j-1][k-1],printf(">(%d,%d,%d)",i-1,j-1,k-1); else f[i][j][k]=f[i-1][j][k-1],printf(">(%d,%d,%d)",i-1,j,k-1); } if(j&&s[j]==')')f[i][j][k]+=f[i-1][j-1][k+1],printf("+(%d,%d,%d)",i-1,j-1,k+1); else f[i][j][k]+=f[i-1][j][k+1],printf("+(%d,%d,%d)",i-1,j,k+1); puts(""); f[i][j][k]%=mod; } } cout<<f[n][m][0]<<endl; } return 0; }
有向图上,找最大的系数w,使得边权均除去w后不存在边权相乘大于1的有向环。
这题比赛场上是另外两位队友负责,思路都是对的,就是没有注意处理好精度问题。
首先w是一个二分答案,找环的过程可以用和找负环类似的做法,进队n次以上则环存在。
但若环的过于大,可能会导致dist数组溢出。
处理方式是对边权和w取log,把乘法转换为加法。
#include<bits/stdc++.h> using namespace std; #define rep(i,a,n) for(int i=a;i<n;i++) #define per(i,a,n) for(int i=n-1;i>=a;i--) #define pb push_back #define SZ(x) ((int)(x).size()) #define mp make_pair #define fi first #define se second #define all(x) x.begin(),x.end() typedef pair<int,int> PII; typedef vector<int> VI; typedef double db; typedef long long ll; const ll mod=1e9+7; template<typename T> inline void read(T &x){ x=0;T fl=1;char tmp=getchar(); while(tmp<'0'||tmp>'9')fl=tmp=='-'?-fl:fl,tmp=getchar(); while(tmp>='0'&&tmp<='9')x=(x<<1)+(x<<3)+tmp-'0',tmp=getchar(); x=x*fl; } const int maxn=1100; int n,m; vector<pair<int,long double>>g[maxn]; long double dist[maxn]; int cnt[maxn]; bool inq[maxn]; bool check(long double w){ queue<int>q; for(int i=1;i<=n;i++){ dist[i]=cnt[i]=0,inq[i]=1; q.push(i); } while(!q.empty()){ int u=q.front();q.pop(),inq[u]=0; cnt[u]++; if(cnt[u]>n)return 0; for(auto r:g[u]){ if(dist[r.fi]<dist[u]+r.se+w){ dist[r.fi]=dist[u]+r.se+w; if(!inq[r.fi]){ q.push(r.fi); inq[r.fi]=1; } } } } return 1; } signed main(){ cin>>n>>m; for(int i=1;i<=m;i++){ long double a,c; int b,d; scanf("%Lf %d %Lf %d",&a,&b,&c,&d); c=log(c/a); g[b].pb(mp(d,c)); } long double l=0,r=1,mid,ans; while(r-l>=1e-8){ mid=(l+r)/2; if(check(log(mid)))l=mid,ans=mid; else r=mid; } printf("%.10Lf\n",ans); return 0; }