美团CodeM2018资格赛赛题官方版本详解（四）——分数

港控/mmm° 2022-05-22 02:06 159阅读 0赞

![20180612214347725][]

![20180612214417760][]

![20180612214447740][]![20180612214555749][]

**解题思路：**

![20180612214628609][]、

**标准程序：**

#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 mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
    // head
    
    typedef unsigned long long score;
    
    const int N=510;
    int n,m,k,c,w[N],sco[N][10],sx,sy,ms[10],c1[N],c2[N];
    score wt[N],s[N],t[N];
    
    int main() {
    	scanf("%d%d%d%d",&n,&m,&k,&c);
    	rep(i,0,m) scanf("%d",w+i);
    	rep(i,0,n) rep(j,0,m) {
    		scanf("%d",&sco[i][j]);
    		if (sco[i][j]==-1) { sx=i; sy=j; }
    	}
    	rep(x,0,c+1) {
    		sco[sx][sy]=x;
    		rep(j,0,m) {
    			ms[j]=0;
    			rep(i,0,n) ms[j]=max(ms[j],sco[i][j]);
    		}
    		rep(j,0,m) {
    			wt[j]=w[j];
    			if (ms[j]==0) { wt[j]=0; continue; }
    			rep(k,0,m) if (j!=k&&ms[k]!=0) wt[j]*=ms[k];
    		}
    		rep(i,0,n) {
    			s[i]=0;
    			rep(j,0,m) s[i]+=wt[j]*sco[i][j];
    			t[i]=s[i];
    		}
    		sort(s,s+n); reverse(s,s+n);
    		rep(i,0,n) {
    			if (t[i]>=s[k-1]) c1[i]++;
    			if ((k!=n)&&t[i]<=s[k]) c2[i]++;
    		}
    	}
    	rep(i,0,n) if (c2[i]==0) puts("1"); else if (c1[i]==0) puts("2"); else puts("3");
    }

[20180612214347725]: /images/20220522/0522343f1b964928a43d6c5714209f39.png
[20180612214417760]: /images/20220522/c3d7c8aa17c74367942f3f08d4609ada.png
[20180612214447740]: https://img-blog.csdn.net/20180612214447740
[20180612214555749]: /images/20220522/bb865d8215854eb18701fad59351cb2d.png
[20180612214628609]: /images/20220522/e8aa37065c64468596135cf7b6aedf46.png