2020年第十四届山东大学程序设计竞赛（重现赛）

C.分栏

Solution

先输出奇数位，再输出偶数位。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e3 + 5;

char s[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>s+1;
    for(int i=1;i<=strlen(s+1);i+=2) cout<<s[i];
    for(int i=2;i<=strlen(s+1);i+=2) cout<<s[i];
    cout<<'\n';
    return 0;
}

D.斐波那契数列？

Solution

令 $x_i=\frac{F_i}{2^i}$ ，由 $Fibonacci$ 递推式可知 $x_i=\frac{x_{i-1}}{2} + \frac{x_{i-2}}{4}$
打表输出答案即可，当变化量过小时，趋向于2，直接输出2即可。

反思:我一开始先预处理了Fibonacci数列，然后再根据Fibonacci数列计算，这样在程序里面会出现精度不够高的问题，能少绕弯子就少绕弯子吧，尤其是高精度要求的题目。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e7 + 5;

double f[N],pre[N];

int main(){
    ll n;cin>>n;
    pre[1]=0.5,pre[2]=0.25;
    double base=8.0;
    double ans=0;
    for(int i=1;i<=n;i++){
        if(i>2) pre[i]=pre[i-2]*0.25+pre[i-1]*0.5;
        if(pre[i]<1e-11) break;
        ans+=pre[i];
    }
    printf("%.9f\n",ans);
    return 0;
}

F.爱买手办的张三

Solution

将所有得到的数的二进制位数记录，二进制枚举加上那些数对应的贡献。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

ll y;
bool v[N];
set<int> s;
unordered_map<int,int> M;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>y;
    cout<<1<<'\n'<<y<<'\n';
    ll k=y,base=0,n=0,id=-1;
    while(k){
        if(k&1) M[++id]=n=base;
        base++;
        k/=2;
    }
    for(int i=0;i<1<<id+1;i++){
        ll tmp=0;
        for(int j=0;j<=id;j++)
            if(i&(1<<j)) tmp+=pow(2,M[j]);
        s.insert(tmp);
    }
    cout<<s.size()<<'\n';
    for(auto c:s) cout<<c<<'\n';
    return 0;
}

红绿灯

Solution

不合法的方案：

出现交叉，如：黄绿，红黄，红绿。
同一个位置有多个不同的颜色。
所构造的方案使得G,Y,R中有一个数＜1。
Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

map<pair<int,string>, bool> v;
int cnt[N];
ll n,T;

bool check(){
    string t;
    for(int i=0;i<T;i++){
        if(t=="Yellow" && v.count(mp(i,"Green"))) return true;
        if(t=="Red" && v.count(mp(i,"Yellow"))) return true;
        if(t=="Red" && v.count(mp(i,"Green"))) return true;
        if(cnt[i]>1) return true;
        if(v.count(mp(i,"Green"))) t="Green";
        if(v.count(mp(i,"Yellow"))) t="Yellow";
        if(v.count(mp(i,"Red"))) t="Red";
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>T;
    int m1=0,m2=INF;
    for(int i=1;i<=n;i++){
        int x;string s;
        cin>>x>>s;
        x=x%T;
        if(s=="Yellow" && x<=0) {cout<<i<<'\n';return 0;}
        if(s=="Red" && x<=1) {cout<<i<<'\n';return 0;}
        if(s=="Green" && x>=T-2) {cout<<i<<'\n';return 0;}
        if(s=="Yellow" && x>=T-1) {cout<<i<<'\n';return 0;}
        if(s=="Green") m1=max(m1,x);
        if(s=="Red") m2=min(m2,x);
        if(m1+1>=m2) {cout<<i<<'\n';return 0;}
        if(!v.count(mp(x%T,s))) v[mp(x%T,s)]=true,cnt[x%T]++;
        if(check()) {cout<<i<<'\n';return 0;}
    }
    cout<<"Correct!\n";
    return 0;
}

L.开学?

Solution

$(x+n-1)~mod~7+1$

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 1e6 + 5;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int x,n;
    cin>>x>>n;
    cout<<(x+n-1)%7+1<<'\n';
    return 0;
}

M.送礼物

Solution

求LIS，并记录对应的值输出即可。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  N = 2e5 + 5;

ll n,p,a[N],f[N],b[N],len,ans[N];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    f[1]=a[1],len=1;b[1]=1;
    for(int i=2;i<=n;i++){
        if(a[i]>f[len]) f[++len]=a[i],b[i]=len;
        else{
            int id=lower_bound(f+1,f+1+len,a[i])-f;
            f[id]=a[i];
            b[i]=id;
        }
    }
    ll k=len,mx=INF;
    for(int i=n;i>0;i--){
        if(!k) break;;
        if(b[i]==k && a[i]<mx){
            ans[k--]=i;
            mx=a[i];
        }
    }
    ll s=p;
    for(int i=1;i<=len;i++)    s+=a[ans[i]];
    cout<<s<<'\n';
    cout<<len<<'\n';
    for(int i=1;i<=len;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}