2020.10.16 【NOIP2014】普及组模拟赛总结

cake

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long n,a[1000111],x;
long long ans;
int main()
{
	freopen("cake.in","r",stdin);
	freopen("cake.out","w",stdout);
	cin>>n;
	for(int i=1; i<=n; i++)
	   scanf("%lld",&a[i]);
	sort(a+1,a+1+n);
	for(int i=n-1; i>=1; i--)
	   ans+=(n-i)*a[i];
	cout<<ans;
	return 0;
}

chess

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int a[110][110];
int n,m,c;
int main()
{
	freopen("chess.in","r",stdin);
	freopen("chess.out","w",stdout);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
     for(int j=1; j<=m; j++)
      {
        scanf("%1d",&a[i][j]);
        if(a[i][j]==1)
          c++;
	  }
	if(n==3&&m==4)
      cout<<c/2;
    else
      cout<<c;
	return 0;
}

sam

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int jyh[100010][20];
int k,ans;
int dfs(int dep,int cw)
{
	if(jyh[dep][cw])
	  return jyh[dep][cw]%1000000007;
	for(int i=max(0,cw-2); i<=min(9,cw+2); i++)
	   jyh[dep][cw]=(jyh[dep][cw]+dfs(dep+1,i))%1000000007;
	return jyh[dep][cw]%1000000007;
}
int main()
{
	freopen("sam.in","r",stdin);
	freopen("sam.out","w",stdout);
    cin>>k;
    if(k==1)
     {
       cout<<10;
       return 0;	
	 }
	for(int i=0; i<=9; i++)
	   jyh[k+1][i]=1;
	for(int i=1; i<=9; i++)
	   ans=(ans+dfs(2,i))%1000000007;
	cout<<ans;
	return 0;
}

similarity

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int b[301][301],a[301][301];
int shul[10],v[301],ans;
int n,m,x,y;
int se_ans()
{
	int js=0;
	for(int i=1; i<=n; i++)
	 for(int j=1; j<=n; j++)
	  {
	  	  if(a[i][j]==1&&b[shul[i]][shul[j]]==1)
	  	    js+=min(a[i][j],b[shul[i]][shul[j]]);
	  }
	return js;
}
void bt(int x)
{
	if(x>n)
	 {
	 	ans=max(ans,se_ans());
	 	return;
	 }
	for(int i=1; i<=n; i++)
	 {
	 	if(!v[i])
	 	 {
	 	   v[i]=1;
	 	   shul[x]=i;
	 	   bt(x+1);
	 	   v[i]=0;
		 }
	 }
}
int main()
{
	//freopen("similarity.in","r",stdin);
	//freopen("similarity.out","w",stdout);
    cin>>n>>m;
	for(int i=1; i<=m; i++)
	 {
	   scanf("%d %d",&x,&y);
	   a[x][y]++;
	 }
	for(int i=1; i<=m; i++)
	 {
	 	scanf("%d %d",&x,&y);
	 	b[x][y]++;
	 }
	bt(1);
	cout<<ans;
	return 0;
}