“美登杯”上海市高校大学生程序设计邀请赛补题

###

A题

题目吓人，实际上就是求子串的个数。长度为n的字符串子串个数为(n+1)*n/2

#include
    
     using namespace std;#define fin freopen("in.txt", "r", stdin)#define fout freopen("out.txt", "w", stdout)#define rep(i,a,n) for(int i=a;i
     
      #define PLL pair
      
       #define PDD pair
       
        #define pi acos(1.0)#define eps 1e-6#define inf 1e17#define INF 0x3f3f3f3f#define N 205const int mod = 998244353;const int P = 1e9 + 7;const int maxn = 1e4+5;int n,q;ll l,r;char s[maxn];int main(){  sca2(n,q);  scs(s);  for(;q;q--)  {    scl2(l,r);    prl((r-l+1)*(r-l+2)/2);  }}
       
      
     
    

B题

三重循环暴力求三角形。除了正三角形，还有倒三角形

#include
    
     using namespace std;#define fin freopen("in.txt", "r", stdin)#define fout freopen("out.txt", "w", stdout)#define rep(i,a,n) for(int i=a;i
     
      #define PLL pair
      
       #define PDD pair
       
        #define pi acos(1.0)#define eps 1e-6#define inf 1e17#define INF 0x3f3f3f3f#define N 205const int mod = 998244353;const int P = 1e9 + 7;const int maxn = 1e5+5;char a[N][N];int vis[26][26][26];int n;int ans;map
        
         p;string s;int main(){  sca(n);  rep(i,0,n+1)scs(a[i]);  ans = 0;  rep(i,0,n+1)  {    rep(j,0,i+1)    {      rep(k,1,n-i+1)      {        s.clear();        s+=a[i][j];        s+=a[i+k][j];        s+=a[i+k][j+k];        sort(s.begin(),s.end());        if(!p[s])        {          p[s] = 1;          ans++;        }      }    }  }  for(int i=n;i>=0;i--)  {    for(int j=0;j<=i;j++)    {      for(int k=1;k<=i&&k<=j&&k<=i-j;k++)      {        s.clear();        s+=a[i][j];        s+=a[i-k][j];        s+=a[i-k][j-k];      //  cout << s<
        
       
      
     
    

C题

dfs进行连通块染色，两个点在k个图中都连通，那么这两个点所染的颜色序列是相同的

用map<vector,int> 存下每个点在k张图的颜色序列出现次数

#include
    
     using namespace std;#define fin freopen("in.txt", "r", stdin)#define fout freopen("out.txt", "w", stdout)#define rep(i,a,n) for(int i=a;i
     
      #define PLL pair
      
       #define PDD pair
       
        #define pi acos(1.0)#define eps 1e-6#define inf 1e17#define INF 0x3f3f3f3f#define N 205const int mod = 998244353;const int P = 1e9 + 7;const int maxn = 1e6+5;int n,m,k;int u,v,color;int vis[maxn];vector
        
         G[maxn],col[maxn];map
         
          
           ,int> p;void dfs(int u){ vis[u] = 1; col[u].push_back(color); for(int i=0;i
          
         
        
       
      
     
    

D题

1.首先，如果每堆石子数量都为1，那么堆数为奇，先手胜，堆数为偶，先手负

2.如果第一堆石子是1，那么先手只能取这1个，相当于先手变成了“后手”。但如果下一堆还是1，那么又变回了先手。所以和1连续的堆数有关，连续堆数为偶，先手胜，连续堆数为奇，后手胜。

3.如果第一堆石子不是1，先手必胜。因为先手可以任意选择成为“先后手”，达到2的必胜态。

#include
    
     using namespace std;#define fin freopen("in.txt", "r", stdin)#define fout freopen("out.txt", "w", stdout)#define rep(i,a,n) for(int i=a;i
     
      #define PLL pair
      
       #define PDD pair
       
        #define pi acos(1.0)#define eps 1e-6#define inf 1e17#define INF 0x3f3f3f3f#define N 205const int mod = 998244353;const int P = 1e9 + 7;const int maxn = 1e6+5;int n,q;int a[maxn],tot[maxn];int cnt;int main(){  sca(n);  cnt=0;  rep(i,1,n+1)  {    sca(a[i]);    a[i+n] = a[i];    if(a[i] == 1)      cnt++;  }  for(int i=n+n;i>=1;i--)  {    if(a[i] == 1)      tot[i] = tot[i+1]+1;    else      tot[i] = 0;  }  rep(i,1,n+1)  {    if(cnt==n)       n%2?prs("First"):prs("Second");    else    {      if(a[i]!=1)        prs("First");      else        tot[i]%2==0?prs("First"):prs("Second");    }  }}
       
      
     
    

I题

签到水题

#include
    
     using namespace std;#define fin freopen("in.txt", "r", stdin)#define fout freopen("out.txt", "w", stdout)#define rep(i,a,n) for(int i=a;i
     
      #define PLL pair
      
       #define PDD pair
       
        #define pi acos(1.0)#define eps 1e-6#define inf 1e17#define INF 0x3f3f3f3f#define N 205const int mod = 998244353;const int P = 1e9 + 7;const int maxn = 1e3+5;int a,b,c,d,n;int v[N];int main(){  sca(n),sca2(a,b),sca2(c,d);  int sum = 0;  rep(i,0,n)  {    sca(v[i]);    sum+=v[i];  }  int ans = sum;  if(sum >= a)  {    ans = sum - b;  }  if(sum >= c)  {    ans = min(ans,sum - d);  }  pri(ans);}