杭电第二场比赛题解

The Oculus

题意：给出一个费波纳希数列的某几个表示a，b，c，问ab的乘积原本是c，但c修改了某一位，求修改了哪位。
思路：直接暴力冲，主要是找出一个适合的mod使得它们形成一一映射，但是似乎用unsigned long long可以直接表示。也就是先进行预处理，然后再进行求出a，b，最后直接遍历求解答案即可。
代码：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=2e6+10;
ull f[maxn];
void inti(){
    f[1]=1,f[2]=2;
    for(int i=3;i<=2e6+7;i++){
        f[i]=f[i-1]+f[i-2];
    }
}
int main(){
    inti();
    int t;
    cin>>t;
    while(t--){
        int n,ch;
        scanf("%d",&n);
        ull a=0,b=0,c=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&ch);
            if(ch) a+=f[i];
        }
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&ch);
            if(ch) b+=f[i];
        }
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&ch);
            if(ch) c+=f[i];
        }
        for(int i=1;i<=2e6+7;i++){
            if(c+f[i]==a*b){
                printf("%d\n",i);
                break;
            }
        }
    }
    return 0;
}

Lead of Wisdom

题意：给出n件物品，一共有k种类型，每件物品有四种属性，问选择出每种类型中一件物品，然后求出使得那个公式值最大的一种方案。
思路：直接爆搜。首先是先将k中类型先分好类来，然后进行爆搜即可。
代码：

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
struct node{
    int a,b,c,d;
};
vector<node> v[100];
int p[100],cnt;
ll ans=0;
void dfs(ll suma,ll sumb,ll sumc,ll sumd,ll index){
    if(index>cnt){
        ll sum=(100LL+suma)*(100LL+sumb)*(100LL+sumc)*(100LL+sumd);
        ans=max(ans,sum);
        return;
    }
    int len=v[index].size();
    for(int i=0;i<len;i++){
        suma+=v[index][i].a;sumb+=v[index][i].b;
        sumc+=v[index][i].c;sumd+=v[index][i].d;
        dfs(suma,sumb,sumc,sumd,index+1);
        suma-=v[index][i].a;sumb-=v[index][i].b;
        sumc-=v[index][i].c;sumd-=v[index][i].d;
    }
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        ans=0;
        cnt=0;
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=k;i++)  v[i].clear();
        memset(p,0,sizeof(p));
        for(int i=0;i<n;i++){
            int type,a,b,c,d;
            scanf("%d%d%d%d%d",&type,&a,&b,&c,&d);
            if(!p[type])  v[++cnt].push_back(node{a,b,c,d}),p[type]=cnt;
            else  v[p[type]].push_back(node{a,b,c,d});
        }
        dfs(0,0,0,0,1);
        printf("%lld\n",ans);
    }
    return 0;
}