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

时间:2021-03-12 14:55:33

链接:https://ac.nowcoder.com/acm/contest/1099#question

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

 #include<bits/stdc++.h>
using namespace std;
char a[][];
int main()
{
int n, m;
while(cin >> n >> m)
{
int x1 = , x2 = ;
int y1 = , y2 = ;
int cnt = ;
for(int i = ;i < n;i++)
for(int j = ;j < m;j++)
cin >> a[i][j];
for(int i = ;i < n;i++)
for(int j = ;j < m;j++)
if(a[i][j] == ''){
cnt++;
x1 = min(x1, i);
x2 = max(x2, i);
y1 = min(y1, j);
y2 = max(y2, j);
}
if((x2 - x1 + )*(y2 - y1 + ) == cnt) cout << "Yes" << endl;
else cout << "No" << endl;
}
return ;
}

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

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll n, k;
void yf(ll &a, ll &b){
ll d = __gcd(a, b);
a /= d;
b /= d;
}
int main()
{
std::ios::sync_with_stdio(false);
while(cin >> n >> k)
{
bool flag = false;
k = min(k, n - k);
ll cnt = n;
ll sum = ;
ll last = ;
for(ll i = ;i <= k;i++){
ll t1 = cnt--;
ll t2 = i;
yf(t1, t2);
yf(t1, last);
yf(sum, t2);
sum *= t1;
last *= t2;
yf(sum, last);
if(sum / last >= INF ){
cout << INF << endl;
flag = true;
break;
}
}
if(!flag)
cout << sum << endl;
} return ;
}

E:记忆化搜索。

 #include<bits/stdc++.h>
using namespace std;
string a;
int ans;
int vis[];
void dfs(int now){
if(now >= a.size())
{
ans++;
return;
}
int t = a[now] - '';
if(!vis[t]){
vis[t] = ;
dfs(now + );
vis[t] = ;
}
if(a[now]- '' != && now + < a.size()){
int tmp = t * + a[now + ] - '';
if(!vis[tmp]){
vis[tmp] = ;
dfs(now + );
vis[tmp] = ;
}
} }
int main()
{ std::ios::sync_with_stdio(false);
while(cin >> a){
ans = ;
dfs();
cout << ans << endl;
} }

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

 #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+;
int main()
{
ll n, a, b, c, d;
while(cin >> n >> a >> b >> c >> d)
{
ll ans = 1LL + (a + b + c + d) % mod * n % mod + n * (n - ) / % mod*((a * b % mod+ b * c % mod + c * d % mod + a * d % mod) % mod) % mod;
cout << ans % mod << endl;
}
return ;
}

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

 #include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+;
int n,m,x,y;
list <int> L[maxn],D[maxn];//L为正序, D为L的倒序
int main()
{
while(cin >> n >> m)
{
for(int i = ;i <= n;i++)
{
L[i].clear(),L[i].push_back(i);
D[i].clear(),D[i].push_back(i);
}
while(m--)
{
cin >> x >> y;
D[y].splice(D[y].end(), D[x]);//将x的倒序拼接在y后面
L[x].splice(L[x].end(), L[y]);//x和y正序拼接
swap(L[x], D[y]);//y的倒序成为x的正序
swap(D[x], D[y]);//x的正序成为x的倒序
L[y].clear();
D[y].clear();
}
cout << L[].size();
for(auto it:L[]) cout << " " << it;
cout << endl;
}
return ;
}