牛客多校赛2（找规律/根号分块 三维括号dp）

G-Link with Monotonic Subsequence

题意：

让max（最长上升子序列个数，最长下降子序列个数）最小

思路：

通过不停不停地找规律得出按照根号分块最好

注意:

比赛的时候把题目想复杂了，以为要不断递归分块呜呜呜

代码：

#include
using namespace std;
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){
        int n;cin>>n;
        double m;m=sqrt(n);int k=ceil(m);
        for(int i=k;i>=1;i--){
            for(int j=i;j<=n;j+=k)cout<' ';
        }
        cout<<'\n';
    }
    return 0;
}

K-Link with Bracket Sequence I

题意：

思路：

f[i][j][k]表示在序列b的第i个字符，与s的最长公共子序列为j，当前的新串左括号比右括号多k个（不允许左括号比右括号少）情况下的方案数。

1 s[j]是左括号

1.1 b[i]的位置放入s[j]  前提k-1≥0

  f[i][j][k] = (f[i][j][k] + f[i-1[j-1][k-1]) % mod;

1.2 b[i]的位置不放入s[j]，而是放入右括号 

  f[i][j][k] = (f[i][j][k] + f[i - 1][j][k + 1]) % mod;

注意：

0.记得dp[0][0][0]=1

1.记得初始化！要初始化是因为动态转移方程式中是根据 s[ j ] 是左括号还是右括号来进行判断的，所以当不放入子序列的时候，也就是j=0时，要遍历i和k进行状态转移

2.内存不要开太大！三位dp的话，dp[250][250][250]会TLE，所以dp[205][205][205]刚好

代码：

#include
using namespace std; 
int dp[205][205][205];//在总序列的第几个 子序列的第几个 左括号比右括号多几个
const int mod=1e9+7;
int main()
{
    int T;cin>>T;int n,m;char s[250];
    while(T--){
        memset(dp,0,sizeof(dp));
        cin>>n>>m;cin>>s+1;
        dp[0][0][0]=1;
        for(int i=1;i<=m;i++)
             for(int k=0;k<=i;k++){
                dp[i][0][k]=(dp[i][0][k]+dp[i-1][0][k+1])%mod;//加入右括号
                if(k>=1)dp[i][0][k]=(dp[i][0][k]+dp[i-1][0][k-1])%mod;//加入左括号
             }
     
        for(int i=1;i<=m;i++){//在总序列的第几个
            for(int j=1;j<=min(i,n);j++){//子序列的第几个
                for(int k=0;k<=i;k++){//左括号比右括号多几个
                    if(s[j]=='('){
                       if(k>=1) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-1][k-1])%mod;
                       //把左括号放进来
                       dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k+1])%mod;
                        //不要左括号 加上右括号
                        //注意这里的条件不同 所以要分开加
                    }
                    else if(s[j]==')'){
                       dp[i][j][k]=(dp[i][j][k]+dp[i-1][j-1][k+1])%mod;
                       if(k>=1) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k-1])%mod;
                    }
                }
            }
        }
        cout<0]<<'\n';
    }
}

J-Link with Arithmetic Progression

题意：

给n个数组，拟合y=kx+b 求拟合的方差最小值

思路一：

因为方差是平方和，所以用三分公差，之后每个ai减去当前的公差，得到n个首项。于是方差的求解变成了（首项i -指定的首项）的平方，从贪心的角度看，指定的首项是首项i的平均数时，方差会最小。

注意：

1.eps设为1e-10来保证精度

2.如果不把double设为long double会运行超时

代码：【1727ms】

#include
using namespace std;
#define double long double
#define eps 1e-10
double a[100005],b[100005];int n;
double f(double mid){
    double sum=0;
    for(int i=1;i<=n;i++){
        b[i]=a[i]-(i-1)*mid;
        sum=sum+b[i];
    }
    sum=sum/n;
    double ans=0;
    for(int i=1;i<=n;i++){
        ans=ans+(sum-b[i])*(sum-b[i]);
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        double l=-1e9,r=1e9;
         while(l+eps
            double lmid=l+(r-l)/3.0,rmid=r-(r-l)/3.0;
            if(f(lmid)<f(rmid)) r=rmid;
            else l=lmid;
        }
    cout<setprecision(12)<<f(l)<<'\n';
 
    }
    return 0;
}

思路二：

最小二乘法

代码：【425ms】

#include
using namespace std;
#define double long double
#define int long long
double a[100005],x1[100005],x2[100005];int n;
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int T;cin>>T;
    for(int i=1;i<=100000;i++){x1[i]=x1[i-1]+i;x2[i]=x2[i-1]+i*i;}
    while(T--){
        cin>>n;double y=0,xy=0; double aa,bb,ans=0;
        for(int i=1;i<=n;i++){cin>>a[i];y+=a[i];xy+=i*a[i];}
        aa=1.0*(x2[n]*y-x1[n]*xy)/(n*x2[n]-x1[n]*x1[n]);
        bb=1.0*(n*xy-x1[n]*y)/(n*x2[n]-x1[n]*x1[n]);
        for(int i=1;i<=n;i++)ans=ans+(a[i]-aa-bb*i)*(a[i]-aa-bb*i);
        cout<setprecision(12)<'\n';
    }
    return 0;
}

D-Link with Game Glitch

 题目：

(讨论区题解的题目翻译) 

小tips:

spfa和dijkstra的算法区别

SPFA模板代码：

从源点开始，把每个遇上的点都放到队列里去。更新时，从队列里抓出来一个点x，点x指向点y，比较 从源点到点y的距离 与 从源点到点x 加上 从点x到点y的路径长度 更新最短的路径。

vectormp[maxn];//用vector建立邻接表
void Spfa(int s) {
    queue<int>v;
    vis[s] = 1; v.push(s); dis[s] = 0;
    while (!v.empty()) {
        int q = v.front();
        v.pop(); vis[q] = 0;
        for (int i = 0; i < mp[q].size(); i++) {
            if (dis[mp[q][i].s1] > dis[q] + mp[q][i].side) {
                dis[mp[q][i].s1] = dis[q] + mp[q][i].side;//更新最短路径。            
                if (!vis[mp[q][i].s1]) {//是在更新新的值条件里面判断，一定特别注意这点
                    v.push(mp[q][i].s1);
                    vis[mp[q][i].s1] = 1;//标记未标记过的点
                }
            }
        }
    }
}

 思路：

若边权积大于1，则表示出现系统漏洞，因此用二分法确定w的大小。

判断边权积大于1的话，讲边权积用log转换，再用spfa判断负环得到结果

#include
using namespace std;
const int N = 1010;
struct Edge { int u, v; double w; };
vector edges, ed;
int n, m;
double dis[N];
bool solve(double x) {
    ed.clear();
    for (auto e : edges) ed.push_back((Edge){e.u, e.v, log(e.w * x)});
    for (int i = 1; i <= n; ++i) dis[i] = -1e9;
    dis[1] = 0;
    for (int k = 1; k < n; ++k)for (auto e : ed) dis[e.v] = max(dis[e.v], dis[e.u] + e.w);
    for (auto e : ed)if (dis[e.v] < dis[e.u] + e.w) return false;
    return true;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        edges.push_back((Edge){b, d, (1.0 * c) / a});
    }
    double L = 0, R = 1;
    while (L + 1e-7 < R) {
        double mid = (L + R) / 2;
        if (solve(mid)) L = mid; else R = mid;
    }
    printf("%.8f", L);
    return 0;
}