A - Tenki
模拟
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
string s, t;
cin >> s >> t;
int res = 0;
for(int i = 0; i < 3; i++) if(s[i] == t[i]) res++;
cout << res << endl;
return 0;
}
B - Power Socket
模拟
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int a, b;
cin >> a >> b;
int t = 1;
int res = 0;
while(t < b){
res++;
t += a - 1;
}
cout << res << endl;
return 0;
}
C - Lower
对每个i都做移动肯定不行,想办法找点性质,发现在一段不递增子序列里最大值肯定是序列长度
中间的点完全可以不用管,维护当前非递增序列长度,当递增时更新
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
int res = 0, t = 0;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0, j = 0; i < n - 1; i++)
if(a[i] >= a[i + 1]) t++;
else
{
res = max(res, t);
t = 0;
}
res = max(res, t);
cout << res << endl;
return 0;
}
D - ModSum
瞪眼出,这种只能算脑筋急转弯,但也不难猜
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
long long n;
cin >> n;
cout << (n - 1) * n / 2 << endl;
return 0;
}
E - League
因为每个人的比赛都是有先后顺序的,很容易往图论想
如果能想到将比赛hash的话,那拓扑排序也是很容易想的
将每场比赛看作一个点,按照先后顺序连边,跑拓扑排序
找最大距离,没有拓扑序说明比赛有冲突,无解
#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 10;
int h[N], e[N], ne[N], idx;
int d[N], n, dist[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int getcode(int x, int y)
{
if(x > y) swap(x, y);
return (x - 1) * n + y;
}
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
vector<vector<int>> a(n + 1, vector<int>(n + 1));
memset(h, -1, sizeof h);
for(int i = 1; i <= n; i++) {
for(int j = 1; j < n; j++) cin >> a[i][j];
for(int j = 1; j < n - 1; j++)
{
add(getcode(i, a[i][j]), getcode(i, a[i][j + 1]));
d[(getcode(i, a[i][j + 1]))]++;
}
}
queue<int> q;
int res = 0;
for(int i = 1; i <= n * n; i++) if(!d[i]) {q.push(i);dist[i] = 1;}
while(!q.empty())
{
int ver = q.front(); q.pop();
res = max(res, dist[ver]);
for(int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
d[j]--;
if(!d[j])
{
q.push(j);
dist[j] = dist[ver] + 1;
}
}
}
for(int i = 1; i <= n * n; i++)
if(d[i]) res = -1;
cout << res << endl;
return 0;
}
F - Engines
F几何题,写不了一点