2019牛客国庆集训派对day1（A, B E F K）

客官°小女子只卖身不卖艺 2023-06-01 11:15 31阅读 0赞

链接：[https://ac.nowcoder.com/acm/contest/1099\#question][https_ac.nowcoder.com_acm_contest_1099_question]

A:可知符合条件的图中间肯定存在一个由1构成的矩形，找到由1构成矩形的边界，判断出现的1的数量等不等于矩形的面积即可。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 char a[15][15];
     4 int main()
     5 {
     6     int n, m;
     7     while(cin >> n >> m)
     8     {
     9         int x1 = 100, x2 = 0;
    10         int y1 = 100, y2 = 0;
    11         int cnt = 0;
    12         for(int i = 0;i < n;i++)
    13             for(int j = 0;j < m;j++)
    14                 cin >> a[i][j];
    15         for(int i = 0;i < n;i++)
    16             for(int j = 0;j < m;j++)
    17                 if(a[i][j] == '1'){
    18                     cnt++;
    19                     x1 = min(x1, i);
    20                     x2 = max(x2, i);
    21                     y1 = min(y1, j);
    22                     y2 = max(y2, j);
    23                 }
    24         if((x2 - x1 + 1)*(y2 - y1 + 1) == cnt) cout << "Yes" << endl;
    25         else cout << "No" << endl;
    26     }
    27     return 0;
    28 }

B：题目所给的式子是组合数的公式C(n,k)，组合数的函数是一个开口向下的二次函数，故有对称性，所以在一边上可以单调递增，我们可以从C(n,0)一直枚举到C(n,min(k, n - k));然后超过1e18则跳出。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 const ll INF = 1e18;
     5 ll n, k;
     6 void yf(ll &a, ll &b){
     7     ll d = __gcd(a, b);
     8     a /= d;
     9     b /= d;
    10 }
    11 int main()
    12 {
    13     std::ios::sync_with_stdio(false);
    14     while(cin >> n >> k)
    15     {
    16         bool flag = false;
    17         k = min(k, n - k);
    18         ll cnt = n;
    19         ll sum = 1;
    20         ll last = 1;
    21         for(ll i = 1;i <= k;i++){
    22             ll t1 = cnt--;
    23             ll t2 = i;
    24             yf(t1, t2);
    25             yf(t1, last);
    26             yf(sum, t2);
    27             sum *= t1;
    28             last *= t2;
    29             yf(sum, last);
    30             if(sum / last >= INF ){
    31                 cout << INF << endl;
    32                 flag = true;
    33                 break;
    34             }
    35         }
    36         if(!flag)
    37         cout << sum << endl;
    38     }
    39 
    40     return 0;
    41 }

E:记忆化搜索。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 string a;
     4 int ans;
     5 int vis[105];
     6 void dfs(int now){
     7     if(now >= a.size())
     8     {
     9         ans++;
    10         return;
    11     }
    12     int t = a[now] - '0';
    13     if(!vis[t]){
    14         vis[t] = 1;
    15         dfs(now + 1);
    16         vis[t] = 0;
    17     }
    18     if(a[now]- '0' != 0 && now + 1 < a.size()){
    19         int tmp = t * 10 + a[now + 1] - '0';
    20         if(!vis[tmp]){
    21             vis[tmp] = 1;
    22             dfs(now + 2);
    23             vis[tmp] = 0;
    24         }
    25     }
    26 
    27 }
    28 int main()
    29 {
    30 
    31     std::ios::sync_with_stdio(false);
    32     while(cin >> a){
    33         ans = 0;
    34         dfs(0);
    35         cout << ans << endl;
    36     }
    37 
    38 }

F:题意：Bobo一开始位于平面上的原点 (0,0)，有四种操作：向右最多移动a步，向上最多移动b步，向左最多移动c步，向下最多移动d步。问执行 n 次操作可以到达多少个不同的点。

思路：只进行一步的操作很简单，分别可以到达坐标轴上离原点最远的 (a, 0), (0, b), (-c, 0), (0, -d)。故包含原点在内共有 1 + a + b + c + d 个点。

多步的话，我们先只看第一象限内的情况：

第一次操作到达x轴上区间 \[1, a\]，第2次到第n次竖直方向上能到达 \[1, (n-1)b)\] ，共 a\*(n-1)b个点；

两次操作到达x轴上区间 \[a+1, 2a\], 第2次到第n次竖直方向上能到达 \[1, (n-2)b)\] ，共 a\*(n-2)b个点；

···

n-1次操作到达x轴上区间 \[(n-2)a+1, (n-1)a\], 第n-1次到第n次竖直方向上能到达 \[1, b\] ，共 a\*b个//点；

// n 次操作到达x轴上最远的a个点 \[(n-1)\*a+1, na\]。

所以答案很简单， 1 + n\*(a + b + c + d) + n(n-1)/2 \* (ab + bc + cd + ad) 。

参考博客：[https://www.cnblogs.com/izcat/p/11618652.html][https_www.cnblogs.com_izcat_p_11618652.html]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 typedef long long ll;
     4 const int mod = 1e9+7;
     5 int main()
     6 {
     7     ll n, a, b, c, d;
     8     while(cin >> n >> a >> b >> c >> d)
     9     {
    10         ll ans = 1LL + (a + b + c + d) % mod * n % mod + n * (n - 1) / 2 % mod*((a * b % mod+ b * c % mod + c * d % mod + a * d % mod) % mod) % mod;
    11         cout << ans % mod << endl;
    12     }
    13     return 0;
    14 }

K：模拟链表，学了大佬的写法，才40行代码，自己手写链表写吐了还WA了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 const int maxn = 1e5+5;
     4 int n,m,x,y;
     5 list <int> L[maxn],D[maxn];//L为正序， D为L的倒序
     6 int main()
     7 {
     8     while(cin >> n >> m)
     9     {
    10         for(int i = 1;i <= n;i++)
    11         {
    12             L[i].clear(),L[i].push_back(i);
    13             D[i].clear(),D[i].push_back(i);
    14         }
    15         while(m--)
    16         {
    17             cin >> x >> y;
    18             D[y].splice(D[y].end(), D[x]);//将x的倒序拼接在y后面
    19             L[x].splice(L[x].end(), L[y]);//x和y正序拼接
    20             swap(L[x], D[y]);//y的倒序成为x的正序
    21             swap(D[x], D[y]);//x的正序成为x的倒序
    22             L[y].clear();
    23             D[y].clear();
    24         }
    25         cout << L[1].size();
    26         for(auto it:L[1]) cout << " " << it;
    27         cout << endl;
    28     }
    29     return 0;
    30 }

转载于:https://www.cnblogs.com/Carered/p/11618382.html

[https_ac.nowcoder.com_acm_contest_1099_question]: https://ac.nowcoder.com/acm/contest/1099#question
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/00a4ab4690d74549a5f338add784c80d.png
[https_www.cnblogs.com_izcat_p_11618652.html]: https://www.cnblogs.com/izcat/p/11618652.html