首页 > 其他分享 >220920 总结

220920 总结

时间:2022-09-20 21:57:14浏览次数:52  
标签:总结 finishTime int 220920 books maxN freopen 100

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

相关文章

  • 归档 220920 | CSP-J 复习
    所以为什么要复习J组所以为什么我连J组都不会,哭唧唧A.加工零件一开始的想法是,如果点\(x\)离\(1\)的距离大于等于\(L\),且与\(L\)奇偶性相同,那么就可行。然......
  • 第四天总结
    1 explicit关键字:只能写在构造函数前面,只是针对Makermaker=10;防止该形式的代码,叫编译器不要优化成Makermaker=Maker(10)2 new和delete2.1 new:从堆区申请空间,做初始......
  • 20220920祭
    20220920t1[SCOI2005]扫雷最初思路显然,对于数值为3或0的格子只有一种情况。考虑从已经确定的摆放情况向周围拓展,直至无法拓展。此时就将所有可以确定的摆放确定,最后只......
  • 2022-2023-1 第三周学习总结
    作业地址:https://www.cnblogs.com/rocedu/p/9577842.html#WEEK03第一周作业:https://www.cnblogs.com/rocedu/p/9577842.html#WEEK03提交情况如图:作业要求:1.学......
  • 20220920
    Get和Post的区别post更安全(不会作为url的一部分,不会被缓存、保存在服务器日志、以及浏览器浏览记录中)post发送的数据更大(get有url长度限制)post能发送更多的数据类型(get......
  • 自我介绍-未来规划-总结
    自我介绍哈喽,大家好,我是印世民,来自湖南怀化,毕业于娄底职业技术学院,现在我是中南林业科技大学涉外学院软件工程专业的一名大三学生,我的爱好是跑步、折纸、打篮球、编程、乒......
  • 联想笔记本进入bios方法总结
    联想电脑如何进入BIOS的方法汇总联想电脑进入BIOS的快捷键有“F2、F1、Del/Delete、NOVO开机”大部分机型都是在开机出现LenovoLogo时按F2或F2,一般来说Think机型按F1,......
  • 2022-2023学年 20211319蓝宇 《信息安全专业导论》第四周学习总结
    作业信息|2020-2021-1信息安全专业导论|https://edu.cnblogs.com/campus/besti/2020-2021-1fois|2020-2021-1信息安全专业导论第三周作业|第三周作业(必学,选做)-作业-2......
  • MySQL-面试题总结
    1.为什么InnoDB存储引擎选择B+Tree索引结构。(1)思路,为什么不采用二叉树和红黑树?普通二叉树,顺序插入,形成链表,大大影响查询效率。红黑树本质上也是二叉树,大数据量,树的......
  • 20220920测试总结
    题目还是挺爽的。P2327[SCOI2005]扫雷原题链接题目分析我们设\(a[i]\)为第\(i\)行的数字,显然如果满足\(a[1]=3\veea[n]=3\)时,方案数为\(0\)呐等于\(0\)。所以接下来......