Press "Enter" to skip to content

Educational Codeforces Round 107 (Rated for Div. 2)

先预祝自己冲击紫名成功

A. Review Site

解题思路

只需要把$1$和$3$放在一个服务器中,$2$放在另一个服务器中就好了

所以答案就是$count(1)+count(3)$

参考代码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#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 PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
#define see(a) cerr<<(#a)<<" = "<<(a)<<endl
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)1e5+5;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef ONLINE_JUDGE

    #endif
    int T;
    cin>>T;
    while (T--)
    {
        int n,res=0,tmp;
        cin>>n;
        rep(i,0,n){cin>>tmp;if(tmp!=2)res++;}
        cout<<res<<endl;
    }
    
    return 0;
}

B. GCD Length

解题思路

我们可以让$c$长度的数值为特殊值,比如让它的值为当前长度情况下最小的$2$的幂。

然后我们可以根据$c$的长度把所对应的值全部找出来

令$p_i$为长度$i$情况下最小的$2$的幂

我们不难得出$p_a (p_b+p_c)$是一组解

参考代码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#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 PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
#define see(a) cerr<<(#a)<<" = "<<(a)<<endl
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)1e5+5;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
ll p[10];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef ONLINE_JUDGE

    #endif
    p[0]=1;
    for (int i = 1,d=1; i <=9; i++,d*=10)
    {
        ll tmp=p[i-1];
        while (tmp<d)tmp<<=1;
        p[i]=tmp;
    }
    int T;
    int a,b,c;
    cin>>T;
    while (T--)
    {
        cin>>a>>b>>c;
        cout<<p[a]<<" "<<p[b]+p[c]<<endl;
    }
    
    return 0;
}

C. Yet Another Card Deck

解题思路

你会发现在所有相同的数值中,只有位于最上面的那个数才有可能会被查询到,换而言之,就是我们只需要考虑每个数最上面的那个值的变化

所以我们用数组来记录最上面的数所对应的下标

每次查询暴力修改即可

时间复杂度为$O(50\times q)$

参考代码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#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 PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
#define see(a) cerr<<(#a)<<" = "<<(a)<<endl
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)1e5+5;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
int a[55];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef ONLINE_JUDGE

    #endif
    int n,q,tmp;
    cin>>n>>q;
    MEM(a,0x3f);
    rep(i,1,n+1){cin>>tmp;if(a[tmp]==INF)a[tmp]=i;}
    while (q--)
    {
        cin>>tmp;
        cout<<a[tmp]<<" ";
        for (int i = 1; i <=50; i++)
        {
            if(a[i]<a[tmp])a[i]++;
        }
        a[tmp]=1;
    }
    
    return 0;
}

D. Min Cost String

解题思路

我们考虑构造最最大的字母为$k$,$cost=0$的最长序列

|是为了找规律用的分隔符
最大字母为C时:aabac|bbc|ca
最大字母为D时:aabacad|bbcbd|ccd|da
最大字母为E时:aabacadae|bbcbdbe|ccdce|dde|ea

我们还发现首尾都是a所以这可以形成一个环,然后根据这个环来输出字符串就好了

参考代码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#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 PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
#define see(a) cerr<<(#a)<<" = "<<(a)<<endl
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)1e5+5;
const int MOD=(int)1e9+7;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef ONLINE_JUDGE

    #endif
    int n,k;
    cin>>n>>k;
    string tmp="";
    for (int i = 0; i < k; i++)
    {
        tmp+=char('a'+i);
        for (int j = i+1; j < k; j++)
        {
            tmp+=char('a'+i);
            tmp+=char('a'+j);
        }
    }
    for (int i = 0; i < n; i++)cout<<tmp[i%tmp.length()];
    cout<<endl;
    return 0;
}

E. Colorings and Dominoes

解题思路

先考虑这样的一种情况

*o
oo

因为横着放和竖着放的颜色是不一样的,所以这种情况的答案就是$2+2=4$,由此得出结论,横竖交叉并不影响答案

所以我们只需要在横竖维度上分别分析连通块对整体的贡献就好了

通过打表我们获得前10个值

3
9
23
57
135
313
711
1593
3527
7737
16839
36409
78279
167481
356807
757305
1601991
3378745
7107015


$$
a_i = 3 \times a_{i-1} – 4 \times a_{i-3}
$$

这个是怎么得到的呢 正常的方法大家应该都知道,这里我就讲一下不正常的方法

线性回归模型:

import numpy as np
from sklearn import linear_model

res = [3,9,23,57,135,313,711,1593,3527,7737,16839,36409,78279,167481,356807,757305,1601991,3378745,7107015]

for k in range(2,6):
    print("k=",k)
    data = []

    for i in range(len(res)-k):
        data.append(res[i:(i+k+1)])

    data = np.array(data)

    x = data[:,:-1]
    y = data[:,-1].reshape(-1,1)

    model = linear_model.LinearRegression()
    model.fit(x, y)
    print("w=",model.coef_)
    print("b=",model.intercept_)
    print("loss=",np.abs(model.predict(x)-y).mean())

输出结果为

k= 2
w= [[-4.00020306  4.00009608]]
b= [-0.09074387]
loss= 0.9555120791102529
k= 3
w= [[-4.00000000e+00 -7.00191016e-10  3.00000000e+00]]
b= [-4.65661287e-10]
loss= 5.132814173691713e-10
k= 4
w= [[-0.46153846 -4.          0.34615385  2.88461538]]
b= [5.82076609e-10]
loss= 6.296924463337442e-10
k= 5
w= [[-1.92503748 -0.68365817 -2.55622189  0.03148426  2.82908546]]
b= [5.82076609e-10]
loss= 6.485225055387543e-10

我们发现$k=3$的时候$loss$最小,所以我们取$k=3$的时候的结果就好了,顺便再验证一下

参考代码

#include <bits/stdc++.h>
#define DEBUG puts("Here is a BUG")
#define MEM(a,b) memset((a),(b),sizeof(a))
#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 PI 3.1415926535897932626
#define all(a) a.begin(),a.end()
#define see(a) cerr<<(#a)<<" = "<<(a)<<endl
typedef long long ll;
using namespace std;
const double eps=1e-8;
const int MAXN=(int)3e5+5;
const int MOD=998244353;
const int INF=0x3f3f3f3f;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
ll kk[MAXN];
ll kk2[MAXN]={0,3,9,23,57,135};
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifndef ONLINE_JUDGE

    #endif
    kk[0]=1;
    rep(i,1,MAXN)kk[i]=(kk[i-1]<<1)%MOD;
    rep(i,4,MAXN)kk2[i]=(3*kk2[i-1]-4*kk2[i-3])%MOD;
    int n,m;
    cin>>n>>m;
    char buf[n][m+1];
    rep(i,0,n)cin>>buf[i];
    ll k=0;
    ll res=0;
    ll cnt=0;
    rep(i,0,n)rep(j,0,m)if(buf[i][j]=='o')cnt++;
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            if(buf[i][j]==buf[i][j-1]&&buf[i][j]=='o')k++;
            else {
                if(k) res=(res+kk[cnt-k-1]*(kk2[k])%MOD)%MOD;
                k=0;
            }
        }
        if(k)res=(res+kk[cnt-k-1]*(kk2[k])%MOD)%MOD;
        k=0;
        
    }
    for (int i = 0; i < m; i++)
    {
        for (int j = 1; j < n; j++)
        {
            if(buf[j][i]==buf[j-1][i]&&buf[j][i]=='o')k++;
            else {
                if(k)res=(res+kk[cnt-k-1]*(kk2[k])%MOD)%MOD;
                k=0;
            }
        }
        if(k)res=(res+kk[cnt-k-1]*(kk2[k])%MOD)%MOD;
        k=0;
    }
    cout<<res<<endl;
    return 0;
}
Subscribe
提醒
guest
0 评论
Inline Feedbacks
View all comments
0
喜欢聆听每一种不同的观点,欢迎评论。x
()
x