没有写 F，不确定我的做法对不对。
评价：什么牛逼场次，代码大赛是嘛，从 A 开始就感觉到不对了，而且题面写的真答辩。
A.Legendary Players
题目分析：
直接按题目模拟即可。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin>>s;
if(s == "tourist") printf("3858\n");
if(s == "ksun48") printf("3679\n");
if(s == "Benq") printf("3658");
if(s == "Um_nik") printf("3648");
if(s == "apiad") printf("3638");
if(s == "Stonefeang") printf("3630");
if(s == "ecnerwala") printf("3613");
if(s == "mnbvmar") printf("3555");
if(s == "newbiedmy") printf("3516");
if(s == "semiexp") printf("3481");
return 0;
}
B.Measure
题目分析：
直接枚举 \(i,j\) 然后判断一下就好.
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;scanf("%d",&n);
for(int i=0; i<=n; i++){
char s = '-';
for(int j=1; j<=9; j++){
if(n % j != 0) continue;
if(i % (n/j)== 0){
s = '1' + j - 1;
break;
}
}
cout<<s;
}
return 0;
}
C.False Hope
题目分析：
一个比较好写的写法就是：直接枚举看到的顺序。
然后枚举 \(i < j < k\)，若 \(p_i,p_j,p_k\) 这三个位于同一条线然后就判断一下是不是值满足条件即可。
对于判断同一条线，行和列是简单的，同一条对角线就是 \(x+y\) 或 \(x-y\) 为定值。
代码：
点击查看代码
#include<bits/stdc++.h>
#define PII pair<int,int>
using namespace std;
PII pos[100];
int a[100],p[100],tot,ans;
bool vis[100];
void chk(){
++tot;
for(int i=1; i<=9; i++){
for(int j=i+1; j<=9; j++){
for(int k=j+1; k<=9; k++){
if(a[p[i]] == a[p[j]] && a[p[j]] != a[p[k]]){
PII b[4] = {pos[p[i]],pos[p[j]],pos[p[k]]};
bool flag = false;
if(b[0].first + b[0].second == b[1].first + b[1].second && b[0].first + b[0].second == b[2].first + b[2].second) flag = true;
if(b[0].first - b[0].second == b[1].first - b[1].second && b[0].first - b[0].second == b[2].first - b[2].second) flag = true;
if(b[0].first == b[1].first && b[0].first == b[2].first) flag = true;
if(b[0].second == b[1].second && b[0].second == b[2].second) flag = true;
if(!flag) continue;
ans += 1;
return;
}
}
}
}
}
void dfs(int now){
if(now == 10){
chk();
return;
}
for(int i=1; i<=9; i++){
if(vis[i]) continue;
p[now] = i; vis[i] = true;
dfs(now+1);
vis[i] = false;
}
}
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
for(int i=1; i<=3; i++){
for(int j=1; j<=3; j++){
scanf("%d",&a[(i-1)*3 + j]);
pos[(i-1)*3 + j] = {i,j};
}
}
dfs(1);
double tmp = tot;
tmp = 1.0 * ans / tmp;
printf("%.9f",1 - tmp);
return 0;
}
D.Minimum Width
题目分析：
所占的行数显然随着宽度的增加而单调不增，所以可以直接二分宽度。
判断占了多少行就是根据题目进行模拟。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+5;
int n,m,l[N];
int get(int len){
int now = len;
int cnt = 1;
for(int i=1; i<=n; i++){
if(l[i] > len) return m + 1;
if(l[i] > now) now = len,++cnt;
if(l[i] <= now) now = now - l[i] - 1;
}
return cnt;
}
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%lld%lld",&n,&m);
for(int i=1; i<=n; i++) scanf("%lld",&l[i]);
int L = 1,R = 1e15,ans = 0;
while(L <= R){
int mid = (L + R) >> 1;
if(get(mid) <= m){
ans = mid;
R = mid - 1;
}
else L = mid + 1;
}
printf("%lld\n",ans);
return 0;
}
E.Bus Stops
题目分析：
一个想法就是建分层图，对于每一个点拆成模 \(p_i\) 下 \(0,1,2,p_i-1\) 这 \(p_i\) 个点，但是不同车站之间无法连边。
所以考虑将每一个点拆成模 \(lcm(p_1,p_2,p_3,\cdots)\) 下的几个点，这样不同车站之间的边就很好连了。
但是其实建分层图是个很傻的行为，因为车站之间只能通过公交车相互到达，所以可以直接枚举 \(lcm(p_1,p_2,p_3,\cdots)\) 个起始时间，然后贪心地得到答案即可。
这里的 \(lcm\) 经过计算不会超过 \(840\)。
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int n,f[850],p[N],t[N];
int solve(int now){
int ans = 0;
for(int i=1; i<n; i++){
int tmp = p[i] - now % p[i];
if(tmp == p[i]) tmp = 0;
now = (now + tmp + t[i])%840;
ans = ans + tmp + t[i];
}
return ans;
}
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int x,y;scanf("%lld%lld%lld",&n,&x,&y);
for(int i=1; i<n; i++) scanf("%lld%lld",&p[i],&t[i]);
for(int i=0; i<=839; i++) f[i] = solve(i);
int q;scanf("%lld",&q);
while(q--){
int k;scanf("%lld",&k);
printf("%lld\n",f[(k+x)%840] + x + y + k);
}
return 0;
}
G.Counting Shortest Paths
题目分析：
注意到我们只需要在所有的边都被删完了，再进行询问。（我一开始以为每一次删边都需要询问，然后就被卡卡卡）
所以可以考虑直接从小到大枚举最短路长度，也就是从 \(1\) 开始一步步扩展直到扩展到 \(n\)。
所以一个直观的想法就是一步步预处理出 \(f[i][j]\) 表示 \(1\) 到 \(i\) 路径长度为 \(j\) 的方案数，\(O(n)\) 显然。
考虑优化，\(f[i][j]\) 的第二维显然只有当 \(j\) 为 \(1\) 到 \(i\) 的最短路时才有意义，所以可以将其它的所有忽略，总状态数变成了 \(O(n)\)。
对于转移，因为是现在的点对其余所有的点产生贡献，所以可以直接一起转移，只有 \(O(m)\) 次转移才是需要特殊注意的，所以只需要管这 \(O(m)\) 次转移，转移的总复杂度为 \(O(m)\)。
设 \(nm\) 同阶，则总时间复杂度为 \(O(n)\)。
代码中为了好写，使用了 set 复杂度会变成 \(O(n \log n)\)
代码：
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
const int MOD = 998244353;
set<int> E[N],cur,lst,tmp;
int cnt[N],a[N];
signed main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n,m;scanf("%lld%lld",&n,&m);
for(int i=1; i<=m; i++){
int u,v;scanf("%lld%lld",&u,&v);
E[u].insert(v);
E[v].insert(u);
}
cnt[n] = 1;
cur.insert(n);
for(int i=1; i<n; i++) lst.insert(i);
while(!cur.empty()){
// for(auto now : cur) printf("%lld ",now);
// printf("\n");
int res = 0;
for(auto now : cur) res = (res + cnt[now])%MOD;
for(auto to : lst) cnt[to] = (cnt[to] + res)%MOD;
for(auto now : cur){
for(auto to : E[now]){
if(lst.find(to) != lst.end()) //避免奇奇怪怪的相互影响
cnt[to] = (cnt[to] - cnt[now] + MOD)%MOD;
}
}
for(auto now : cur){
int tot = 0;
for(auto to : E[now]) a[++tot] = to;
for(int i=1; i<=tot; i++){
E[a[i]].erase(now);
E[now].erase(a[i]);
}
}
swap(tmp,lst);
cur.clear(),lst.clear();
for(auto i : tmp){
if(cnt[i]){
cur.insert(i);
if(i == 1){
printf("%lld\n",cnt[1]);
return 0;
}
}
else lst.insert(i);
}
tmp.clear();
}
printf("-1\n");
return 0;
}
- 题解 Beginner AtCoder Contest 319beginner atcoder contest 319 题解beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334