浪潮1024工程师文化节编程大赛

1.https://nanti.jisuanke.com/t/T1649

简单模拟，对其从横方向和竖方向进行暴力搜索即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N=1010;
int n;
int a[N][N];
int ans[N][N];
int cnt=-1;
signed main()
{
    IOS;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]==0)
            {
                for(int h=1;h<=n;h++)
                {
                    ans[i][j]+=a[i][h];
                }
                for(int s=1;s<=n;s++)
                {
                    ans[i][j]+=a[s][j];
                }
            }
        }
        
    }
      for(int i=1;i<=n;i++)
      {
          for(int j=1;j<=n;j++)
          {
              if(cnt<ans[i][j])
              cnt=ans[i][j];
          }
      }
    cout<<cnt<<endl;
    return 0;
}

2、https://nanti.jisuanke.com/t/A1701

普通LIS为n^2级别，超时，这里学习的人家的思想，用一个m[]来表示以某价格结尾的最大销售量，dp[]则表示以第i个物品结尾（注意是物品的数量）最大销售量，；然后后面分别将没有加进来的依次加进来（满足次序是递增的）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 //#define int long long 
 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 5 const int N=1e5+10;
 6 int t;
 7 int n,d;
 8 int a[N];
 9 int LIS()
10 {
11     /*int dp[N];
12     dp[1]=1;
13     for(int i=2;i<=n;i++)
14     {
15         int maxx=0;
16         for(int j=1;j<i;j++)
17         {
18             if(dp[j]>maxx&&j<i&&abs(p[i]-p[j])<=d)
19             maxx=dp[j];
20         }
21         dp[i]=maxx+1;
22         if(dp[i]>ans)
23         {
24             ans=dp[i];
25         }
26     }
27     return ans;*/
28     int ans=-1;
29     int dp[N];
30     int m[N];
31     memset(dp,0,sizeof(dp));
32     memset(m,0,sizeof(m));
33     for(int i=1;i<=n;i++)
34     {
35         dp[i]=1;
36         for(int j=max(1,a[i]-d);j<=min(a[i]+d,100000);j++)
37         {
38             dp[i]=max(dp[i],m[j]+1);
39         }
40         m[a[i]]=max(m[a[i]],dp[i]);
41         ans=max(ans,dp[i]);
42     }
43     return ans;
44 }
45 signed main()
46 {
47     IOS;
48     cin>>t;
49     while(t--)
50     {
51         cin>>n>>d;
52         for(int i=1;i<=n;i++)
53         {
54             cin>>a[i];
55         }
56         cout<<LIS()<<endl;
57     }
58     return 0;
59 }

3.https://nanti.jisuanke.com/t/T1395

思路很简单，比对输入字串和目标字串，如果不同则反转当前的字符，并且步数加一；

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define int long long 
 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 5 string a,b;
 6 int cnt;
 7 char solved(int c)
 8 {
 9     if(c=='*')
10     {
11         c='o';
12     }
13     else
14     {
15         c='*';
16     }
17     return c;
18 }
19 signed  main()
20 {
21     IOS;
22     getline(cin,a);
23     getline(cin,b);
24     for(int i=0;i<a.length()-1;i++)
25     {
26         if(a[i]!=b[i])
27         {
28             a[i]=solved(a[i]);
29             a[i+1]=solved(a[i+1]);
30             cnt++;
31         }
32     }
33     if(a==b)
34     {
35         cout<<cnt<<endl;
36     }
37     else
38     {
39         cout<<"No Answer."<<endl;
40     }
41     return 0;
42 }

4.https://nanti.jisuanke.com/t/T1412

dfs前驱记录题

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define int long long 
 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 5 const int N=1e5+10;
 6 int t;
 7 int n,m;
 8 vector<int>g[N];
 9 bool vis[N];
10 int pre[N];
11 void dfs(int x)
12 {
13     for(int i=0;i<g[x].size();i++)
14     {
15         if(!pre[g[x][i]])
16         {
17             pre[g[x][i]]=x;
18             dfs(g[x][i]);
19         }
20     }
21 }
22 signed main()
23 {
24     IOS;
25     cin>>t;
26     while(t--)
27     {
28         memset(g,0,sizeof(g));
29         memset(pre,0,sizeof(pre));
30         cin>>n>>m;
31         int s,t;
32         for(int i=1;i<=n-1;i++)
33         {
34             cin>>s>>t;
35             g[s].push_back(t);
36             g[t].push_back(s);
37         }
38         pre[m]=-1;
39         dfs(m);
40         for(int i=1;i<=n;i++)
41         {
42             cout<<pre[i]<<" ";
43         }
44     }
45     return 0;
46 }