SMU Summer 2024 Contest Round 4

1.H and V

原题链接：

http://162.14.124.219/contest/1008/problem/B

二进制枚举行列即可

#include <bits/stdc++.h>
#define int long long
#define PII pair<int,int>
using namespace std;
int n,m,k;
char a[10][10];
signed  main() {
    ios::sync_with_stdio(false);cin.tie(0);
  	cin>>n>>m>>k;
  	int sum=0;
  	for(int i=0;i<n;++i){
  		for(int j=0;j<m;++j){
  			cin>>a[i][j];
  			if(a[i][j]=='#') sum++;
  		}
  	}

  	int cnt=0;
  	int ans=0;
  	 for(int i=0;i<(1<<n);++i){
  	 	for(int j=0;j<(1<<m);++j){
  	 		cnt=0;
  	 		for(int r=0;r<n;++r){
  	 			for(int c=0;c<m;++c){
  	 				if( ((i&(1<<r)) || (j&(1<<c)))&& a[r][c]=='#') cnt++;
  	 			} 
  	 		}
  	 		if(cnt==sum-k) ans++;
  	 	}
  	 }

  	 cout<<ans<<endl;

    return 0;
}

2.Moving Piece

原题链接：

http://162.14.124.219/contest/1008/problem/C

查找循环节并存入ve中，并贪心取最优

 #include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 9;
int Pp[maxn],Cc[maxn],mp[5009];
int a[maxn],sum[maxn];
vector<int>ve[5009];
signed  main()
{
    int n,k;
    int x;
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        Pp[i]=a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        Cc[i]=x;
    }
    int ans=-1e18;
    for(int i=1;i<=n;i++)
    {
        int now=i;
       memset(mp,0,sizeof mp);
        while(1)
        {
            now=Pp[now];
            if(mp[now]==1) break;
            mp[now]=1;
            sum[i]+=Cc[now];
            ve[i].push_back(Cc[now]);
        }
        int len=ve[i].size();
        int d=k/len;
        int m=k%len;
        now=0;
        if(sum[i]>0)
        {
            if(m==0)
            {
                now=(d-1)*sum[i];
                m=len;
            }
            else now=d*sum[i];
            for(int j=0;j<m;j++) now+=ve[i][j],ans=max(ans,now);
        }
        else
        {
            if(d==0)
            {
                for(int j=0;j<m;j++) now+=ve[i][j],ans=max(ans,now);
            }
            else
            {
                for(int j=0;j<len;j++) now+=ve[i][j],ans=max(ans,now);
            }
        }
    }
    cout<<ans;
    return 0;
}

3.Sum of Divisors

原题链接：

http://162.14.124.219/contest/1008/problem/D

反着回去找会爆，那就正着去找

 #include <bits/stdc++.h>
#define int unsigned long long
#define PII pair<int,int>
using namespace std;
int a[10000010];
signed main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j+=i)
            a[j]++;
    }
    int sum=0;
    for(int i=1;i<=n;i++)
        sum+=a[i]*i;
    cout<<sum;
    return 0;
}