220920 总结
预计:\(100+100+100\)
实际:\(100+100+10\)
T1
注意到 \(K\leq100\) 所以写了个类似 dp 的东西
复杂度大概是 \(O(NMK)\) ?
此时大概过去了 30min
#include<bits/stdc++.h>
using namespace std;
const int maxN = 110;
int N,M,MOD;
unordered_set<int> S[maxN][maxN];
int A[maxN][maxN];
vector<int> V;
int main(){
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
scanf("%d%d%d",&N,&M,&MOD);
for(int i = 1;i<=N;i++){
for(int j = 1;j<=M;j++){
scanf("%d",&A[i][j]);
A[i][j] %= MOD;
}
}
S[0][1].insert(1);
for(int i = 1;i<=N;i++){
for(int j = 1;j<=M;j++){
for(auto k : S[i-1][j]) S[i][j].insert(k*A[i][j]%MOD);
for(auto k : S[i][j-1]) S[i][j].insert(k*A[i][j]%MOD);
}
}
printf("%d\n",int(S[N][M].size()));
for(auto i : S[N][M]) V.push_back(i);
sort(V.begin(),V.end());
for(auto i : V) printf("%d ",i);
return 0;
}
T2
本来想写拓扑排序但一想要缩点再一看数据范围就没想去写拓扑
寻找所有的入度为 \(0\) 的点,并以之为始点进行 DFS
怕有遗漏的点有扫了一遍 \(N\) 个点看是不是都经过了
复杂度大概是 \(O(N^2)\)
此时大概又过去了 30min
#include<bits/stdc++.h>
using namespace std;
const int maxN = 1010;
vector<int> G[maxN];
int inD[maxN];
int N;
bool vis[maxN];
void dfs(int k){
vis[k] = 1;
for(auto i : G[k]) if(!vis[i]) dfs(i);
}
vector<int> V;
int main(){
freopen("news.in","r",stdin);
freopen("news.out","w",stdout);
scanf("%d",&N);
for(int i = 1;i<=N;i++){
for(int j = 1;j<=N;j++){
int t;
scanf("%d",&t);
if(t){
G[i].push_back(j);
inD[j]++;
}
}
}
int ans = 0;
for(int i = 1;i<=N;i++) if(inD[i] == 0) V.push_back(i);
for(auto i : V){
if(!vis[i]){dfs(i);ans++;}
}
for(int i = 1;i<=N;i++){
if(!vis[i]){dfs(i);ans++;}
}
printf("%d",ans);
return 0;
}
T3
一眼模拟 再一细看 哦是大模拟 乐
思路挺简单的倒是不太好写
遍历每个时间点,扫一遍所有人的借书信息 同时维护书和人的状态
写写改改改改写写
写完就马上到点了 测了下样例过了就直接交了
后来发现是 \(0\leq s\lt1000\) 而不是 \(0\lt s \leq 1000\) (少算了一本书的次数
(为什么我不直接加到结果里而是加到书上最后相加输出啊 我不理解
#include<bits/stdc++.h>
using namespace std;
const int maxN = 120;
struct Book{
int readTimes;
int finishTime;
bool isReading;
}B[1010];
struct Reader{
int arriveTime;
int finishTime;
int num;
int books[8];
int t[8];
bool read[8];
Reader(){
arriveTime = finishTime = num = 0;
memset(books,0,sizeof(books));
memset(t,0,sizeof(t));
memset(read,0,sizeof(read));
}
}A[maxN];
int T,N;
int main(){
freopen("reading.in","r",stdin);
freopen("reading.out","w",stdout);
scanf("%d%d",&T,&N);
for(int i = 1;i<=N;i++){
Reader t;
scanf("%d",&t.arriveTime);
t.finishTime = t.arriveTime;
int k;
scanf("%d",&k);
t.num = k;
for(int j = 1;j<=k;j++){
scanf("%d%d",&t.books[j],&t.t[j]);
}
A[i] = t;
}
for(int t = 0;t<T;t++){
for(int i = 1;i<=N;i++){
bool isReading = false;
if(A[i].finishTime > t) continue;
for(int j = 1;j<=A[i].num;j++){
if(A[i].read[j]) continue;
if(B[A[i].books[j]].finishTime <= t){
isReading = true;
A[i].read[j] = true;
A[i].finishTime = t + A[i].t[j];
B[A[i].books[j]].finishTime = A[i].finishTime;
B[A[i].books[j]].readTimes++;
break;
}
}
if(!isReading){
int nextTime = 2e9;
int b;
for(int j = 1;j<=A[i].num;j++){
if(A[i].read[j]) continue;
if(nextTime > B[A[i].books[j]].finishTime){
nextTime = B[A[i].books[j]].finishTime;
b = j;
}
}
if(nextTime >= T) continue;
A[i].read[b] = true;
B[A[i].books[b]].finishTime += A[i].t[b];
A[i].finishTime = B[A[i].books[b]].finishTime;
B[A[i].books[b]].readTimes++;
}
}
}
int ans = 0;
for(int i = 1;i<=1000;i++) ans += B[i].readTimes;
printf("%d",ans);
return 0;
}
标签:总结,finishTime,int,220920,books,maxN,freopen,100
From: https://www.cnblogs.com/burnling/p/16712677.html