Tarjan练习 CODEVS1332 上白泽慧音

这个题。。。须臾dalao看到会高兴的2333

虽然图论学了很久。。但tarjan还是懒得学。。。

于是今天放假在机房做了这个例题。。。特地加了很多注释(翻以前写的渗透工具代码都看不懂了。。吓得我赶紧打了注释)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
#include <iostream>//甚至没有oi库、、、 
#include <algorithm>//没用到算法库啊。。。 
#include <stack>
using namespace std;
int x,mins=0;
int oldbest=99999999999;
int m,n,tot,head[5005];
int dfn[5005],low[5005],sccno[5005],num,cnt,sum[5005],ans,mark;
stack<int>EDP;
//DFN[ i ] : 在DFS中该节点被搜索的次序(时间戳)
//LOW[ i ] : 为i或i的子树能够追溯到的最早的栈中节点的次序号
//当DFN[ i ]==LOW[ i ]时,为i或i的子树可以构成一个强连通分量。
struct node { //邻接表储存,你高兴就好,毕竟减小空间。。。 
	int to; //相邻点指向 
	int next;  //论此点一个有多少个相邻点
} Graph[100005];
 
void add(int x,int y) {//加边函数 
	tot++; //+1s准备为下一位做准备 
	Graph[tot].to=y;  //记录连接点 
	Graph[tot].next=head[x];   //遍历时往前跑用的(讲道理,改进下就不需要了,可以省空间) 
	head[x]=tot;//记录连接点数 
}
void tarjan(int u) {
	int i,j;
	dfn[u]=low[u]=++num;//无回溯时dfn==low要按dfs序赋值 
	EDP.push(u);//压到栈中,为后来回溯做检查准备 
	for (i=head[u]; i; i=Graph[i].next) {//枚举每条边。PS i和graph不同步,i只是计数,graph向前找相应位数 
		int v=Graph[i].to;//确立连接点 
		if (!dfn[v]) {//没访问过,不然序号不可能为零,所以我们不需要设立vis数组来“占用额外空间 ” 
			tarjan(v);//继续向下找,遍历 
			low[u]=min(low[u],low[v]);
			//3.如果此时(时间为dfn[u]时)v不在栈中,u的low值为两点的low值中较小的一个。
		} else if (!sccno[v]) //还未曾属于那个强联通集合 
			low[u]=min(low[u],dfn[v]);
		//4.如果此时(时间为dfn[u]时)v在栈中,u的low值为u的low值和v的dfn值中较小的一个。
	}
	if (low[u]==dfn[u]) {//5
		cnt++;//++分量数序号
		while (true) {
			x=EDP.top();//取出并弹出 
			EDP.pop();
			sccno[x]=cnt;//标记顶点x属于第cnt个强连通分量
			sum[cnt]++;//该序号的分量点数
			if (x==u) break;
		}
		// --------此题的选择---> tarjan算法之外的内容      //
		if (sum[cnt]>=ans) {//记录强连通分量的最值
			if(sum[cnt]==ans) { //如果位数相等那么直接找两者最小值对比 
				for (i=1; i<=n; i++) {
					if (sccno[i]==cnt) {//找到该最小值 
						mins=i;
						break;//找到最小就跳 
					}
				}
				if(mins<oldbest) {//如果比他小那么就mark并重记录最小值 
					ans=sum[cnt];//最多数量 
					mark=cnt;//最大分量数 的序号
					oldbest=mins;//记录最前值 
				}
			} 
			else{ //如果大于那么就不mark直接记录最小值 
				for (i=1; i<=n; i++) {
					if (sccno[i]==cnt) {//找到该最小值 
						mins=i;
						break;//找到最小就跳 
					}
				}
				ans=sum[cnt];
				mark=cnt;//最大分量数 的序号
				oldbest=mins;//记录最小值 
			}
		}
		//  -------  <---选择 此题的选择,tarjan之外的内容 //
	}
 
}
int main() {//main我就没什么需要说的了。。。 
	int i,j,x,y,t;//t就是确立是单向边,还是双向边的一个参数。。。 
	scanf("%d%d",&n,&m);
	for (i=1; i<=m; i++) {
		scanf("%d%d%d",&x,&y,&t);
		add(x,y);
		if (t==2)
			add(y,x);
	}
	for (i=1; i<=n; i++)
		if (!dfn[i]) tarjan(i);
	printf("%d\n",ans);
	for (i=1; i<=n; i++)  //找到mark标记,输出对应强联通节点 
		if (sccno[i]==mark) printf("%d ",i);
	return 0;
}

 

NOIP初赛退役选手

mdzz。。。我还以为初赛属于随便过的那种。。。

结果今年跟考数学一样,平常一直用sort。。。结果竟然要手写快排。。。还有求树的重心(这尼玛什么鬼啊),选择题都还好说。。。md程序阅读题错了三,程序填空当根据上下文猜测题意来做的。。。md没救了。。。

不说了,没事我初赛退役了

树状数组练习 CODEVS1217 借教室

题目描述 Description

在大学期间,经常需要租借教室。大到院系举办活动,小到学习小组自习讨论,都需要

向学校申请借教室。教室的大小功能不同,借教室人的身份不同,借教室的手续也不一样。

面对海量租借教室的信息,我们自然希望编程解决这个问题。

我们需要处理接下来n天的借教室信息,其中第i天学校有ri个教室可供租借。共有m份

订单,每份订单用三个正整数描述,分别为dj, sj, tj,表示某租借者需要从第sj天到第tj天租

借教室(包括第sj天和第tj天),每天需要租借dj个教室。

我们假定,租借者对教室的大小、地点没有要求。即对于每份订单,我们只需要每天提

供dj个教室,而它们具体是哪些教室,每天是否是相同的教室则不用考虑。

借教室的原则是先到先得,也就是说我们要按照订单的先后顺序依次为每份订单分配教

室。如果在分配的过程中遇到一份订单无法完全满足,则需要停止教室的分配,通知当前申

请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。

现在我们需要知道,是否会有订单无法完全满足。如果有,需要通知哪一个申请人修改

订单。

输入描述 Input Description

第一行包含两个正整数n, m,表示天数和订单的数量。

提高组  day2 

 

第二行包含n个正整数,其中第i个数为ri,表示第i天可用于租借的教室数量。

接下来有m行,每行包含三个正整数dj, sj, tj,表示租借的数量,租借开始、结束分别在

第几天。

每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。

输出描述 Output Description

如果所有订单均可满足,则输出只有一行,包含一个整数 0。否则(订单无法完全满足)

输出两行,第一行输出一个负整数-1,第二行输出需要修改订单的申请人编号。

最后俺那个算法只能过一个点,然后俺老师帮俺改了下,但是还是只能过几个点

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
#define MAXN 2000100
using namespace std;
ll a[MAXN],c[MAXN];
ll n,m;
ll days,pays,classopen1[1000001];

inline ll read() {
ll x=0,f=1;
char ch=getchar();
while(ch>’9’||ch<‘0’) {
if(ch==’-‘)f=-1;
ch=getchar();
}
while(ch>=’0’&&ch<=’9′) {
x=x*10+ch-‘0’;
ch=getchar();
}
return x*f;
}
struct tree_array_single {
ll arr[MAXN];
void add( ll x, ll n) {
while(x<=days)arr[x]+=n,x+=lowbit(x);
}
ll sum( ll x) {
ll sum=0;
while(x)sum+=arr[x],x-=lowbit(x);
return sum;
}
} T1,T2;
//inline void reset(){CLR(T1.arr,0); CLR(T2.arr,0);}
inline void add( ll x, ll n) {
T1.add(x,n);
//T2.add(x,x*n);
}
inline void update( ll L, ll R, ll n) {
add(L,n);
add(R+1,-n);
}
ll qs(ll x){
return T1.sum(x);
}
inline ll sum( ll x) {
return (x+1)*T1.sum(x)-T2.sum(x);
}
inline ll query( ll L, ll R) {
return sum(R)-sum(L-1);
}
ll amount,st,en;
int main()
{

days=read();
pays=read();
// ll min=1000000000;
for(ll i=1;i<=days;i++){
classopen1[i]=read();
//add(i,classopen1[i]-classopen1[i-1]);
}
for( ll i=1;i<=pays;i++)
{
// min=1000000000;
amount=read();
st=read();
en=read();
//cout<<“q,i”<<query(i,i)<<endl;

//prllf(“AMOUNT—%d—\n”,payday[i].amount);
update(st,en,amount);
//cout<<“i “<<T1.sum(i)<<endl;
for( ll j=st;j<=en;j++)
{ ll tm=qs(j);
// cout<<“q j “<<amount<<” “<<j<<” “<<tm<<endl;
if (tm>classopen1[j]) {
//ll thiss=i;
printf(“-1\n%lld”,i);
return 0;
}
}
}
printf(“0”);
return 0;
}

树状数组练习 CODEVS1082 线段树练习3

题目描述 Description

给你N个数,有两种操作:
1:给区间[a,b]的所有数增加X
2:询问区间[a,b]的数的和。

输入描述 Input Description

第一行一个正整数n,接下来n行n个整数,

再接下来一个正整数Q,每行表示操作的个数,

如果第一个数是1,后接3个正整数,

表示在区间[a,b]内每个数增加X,如果是2,

表示操作2询问区间[a,b]的和是多少。

pascal选手请不要使用readln读入

输出描述 Output Description

对于每个询问输出一行一个答案

样例输入 Sample Input

3

1

2

3

2

1 2 3 2

2 2 3

样例输出 Sample Output

9

 

怕记不住算法具体内容。。。去找了一份写得好的来记上。。

#include <bits/stdc++.h>
#include <malloc.h>
#include <memory.h>
#define lowbit(x) x&(-x)
#define ll long long
#define MAXN 200010
using namespace std;
ll a[MAXN],c[MAXN];
ll n,m;

//读入优化》
inline ll read() {
int x=0,f=1;
char ch=getchar();
while(ch>’9’||ch<‘0’) {
if(ch==’-‘)f=-1;
ch=getchar();
}
while(ch>=’0’&&ch<=’9′) {
x=x*10+ch-‘0’;
ch=getchar();
}
return x*f;
}

//读入优化《
struct tree_array_single {
ll arr[MAXN];
void add(ll x,ll n) {
while(x<=MAXN)arr[x]+=n,x+=lowbit(x);
}
ll sum(ll x) {
ll sum=0;
while(x)sum+=arr[x],x-=lowbit(x);
return sum;
}
} T1,T2;
//inline void reset(){CLR(T1.arr,0); CLR(T2.arr,0);}
inline void add(ll x,ll n) {
T1.add(x,n);
T2.add(x,x*n);
}
inline void update(int L,int R,ll n) {
add(L,n);
add(R+1,-n);
}
inline ll sum(ll x) {
return (x+1)*T1.sum(x)-T2.sum(x);
}
inline ll query(int L,int R) {
return sum(R)-sum(L-1);
}
//int c1[MAXN],c2[MAXN];
int main() {
n=read();
for(ll i=1; i<=n; i++) {
a[i]=read();
add(i,a[i]-a[i-1]);
}
m=read();
for(ll i=1; i<=m; i++) {
ll h;
h=read();
if(h==1) {
ll b,c,d;
b=read();
c=read();
d=read();
update(b,c,d);
} else {
ll b,c;
b=read();
c=read();
printf(“%lld\n”,query(b,c));
}
}
}

项目开发进度已崩

noip好像马上就要开始了QAQ。。。还开发个篮子,整天各种算法

其实我只是想来水一篇博文而已。。。

现在赤弦的引擎基本上已经完工,特征量还不是很够。。。主防框架已出。。。剩下的就是各种填充。。。

礼花弹我又加了几个exp,把xss扫描写完就可以发布了。。。

最近对源码加密很痴迷。。。一直在写一个源码加密器,还没想好名233.。。。

可以关注MAX技术组开发区和官网来得知最新消息QAQ

MAXjishuzu.ml

MAXkaifa.ml

渗透朋友的站点我也是装作四处看风景

今天在群里跟青涩他们闹着玩。。。说是要渗透下他的博客试试。。。

当时我的心情就崩溃了。。。 整站搞的一般没有什么UAF,我觉得自己要栽了。。。

果然,试了试手里的几个漏洞利用EXP,没有什么成果。。。果断又爬了下连接,没有php啥的动态网页可供注入。。。

结果他就正好说他的插件啥的,给我把它插件的一个后台连接发了过来。。。朋友们!,你们估计以为我有那个插件的漏洞利用EXP?很不幸没有,不过我突然想起来了后台更可以试试啊,我就抱着试试的心理,动用了点社工知识,撞库攻击,不料五秒钟之后成功了。。。

其实我倒挺想试试那几个exp的。。。不过没用到还。。。当然欢迎继续关注礼花弹的开发。。。exp列表会继续扩充qq%e6%88%aa%e5%9b%be20160929160202

剩下的我就不说了,大家肯定明白该利用IIS6的各种解析漏洞和翻插件啥的拿到shellQAQ

我和青涩当时的心情估计都是QAQ 

渗透测试 溢出分析套路2ND

i am too lazy to write the blog

so

我把我在吾爱写的帖子搬过来了23333333http://www.52pojie.cn/thread-521827-1-1.html

首先我们先来试一下本地溢出的漏洞。。。当然,我们得自己构造一个来尝试,memcpy函数就是个很好的例子。。。
编译语言 c
编译器vc++

 
01
02
03
04
05
06
07
08
09
10
11
#include"stdio.h"
#include"string.h"
main()
{
int i;
char a[4]="s",b[20]="ssssssssssssssssss";
i=sizeof(b);
memcpy(a,b,i);
printf("a=%s\nb=%s",a,b);
return 0;
}

代码部分不多做介绍,至于为什么用vc++?因为其他编译器大多都会做溢出保护,当然,这些都可以通过技术手段绕过。。。
学过c的同学一眼肯定就能看出,在调用memcpy中发生了溢出,a只有五个字节的空间,但要把b全复制进去,多余的16个空间就发生了溢出,现在开始手动调试
od载入。004014E0 >/$  55            push ebp

ctrl g搜索一下函数“memcpy”
来到这里00401160 > $  55            push ebp
f2下一个断点,然后f9让程序跑起来。跑到我们的断点处停下,然后ctrl f9将这个函数跑完,中途可能要跑完好几个函数。。。中途可以顺便看一下ecx:0018FF2C   这个地址内的数据是一堆s,继续跑,来到这里0040108B  |.  83C4 0C       add esp,0xC
可以看到上一行就是00401086  |.  E8 D5000000   call memcpy                              ; \memcpy
此时f8忽略call单步下去,直到运行到retn,此时cpu会取出esp所存储的内存数据,传给eip,作为一条指令所在的内存地址,此时看一下寄存器ESP:0018FF4C
再查一下堆栈窗口,看下这个0018FF4C地址存储什么数据?0018FF4C  : 73737373
73?大家可能已经明白了,73就是我们用的小写s的16进制形式,我们的溢出数据用的就是s。
我们再压一下f9,程序运行出错,可以在异常信息中看到,偏移为73737373

很明显,多余的s覆盖了memcpy的返回地址,而73737373并不存在,程序就boom了
但是如果我们不用s,而把多余的数据换成我们精心设计的shellcode呢?一次溢出攻击就发动了。
至于shellcode怎么写?
首先我们需要算出溢出是第几个数据处发生的,这个用堆栈窗口稍微一算就ok,我无需多说了、、、
也可以在vc++中完成,以asm内联汇编的形式写一段你需要的攻击代码,然后转成16进制码即可,如果我们,把shellcode代替那多余的16的s来使用,咳咳、、、
但是我们需要多说几句话,首先,在合法的数据后面可是不能直接写攻击代码的~我们要绕一下。在asm中攻击代码的前面,我们要多加一条jmp esp或者是call esp。这是为何呢?
程序每运行一次,堆栈的内存地址都会发生变化,shellcode则分布的杂乱无章,怎么破呢?用esp,esp永远代表堆栈地址所在位置,于是,我们先用调到esp的指令来覆盖,就能达到我们的目的,至于jmp esp的所在内存的地址是什么?各个系统都不一样,我们需要用到一个findjmp的工具来查询,而查到后注意,不能直接写上,首先也要分成4对来储存,例如“x47“然后我们需要把顺序全变过来,如果原来是x12 x45 x09,现在就要是x09 x45 x12,这是因为windows系统的底层设计问题,,,我们不多说。此时第一行shellcode是jmp esp,但注意!还没有完成,程序在溢出后,会崩溃,而崩溃中,就会发生偏移,此时我们可以通过od把偏移量算出来,在jmp esp与攻击代码直接加上偏移量大小的无用数据,当然,懒的话还有个办法,直接加上10个无用字母,基本上偏移量也不会更大了。。。
此时我们把精心设计好的shellcode换掉多余的一堆s,就能达到你攻击代码想实现的目的。

当然这只是本地溢出?至于远程溢出,远程服务可能是以加密的数据来传输的,也可能是明文传输的,相对而言,远程服务为了效率,明文传输更多,,而且这跟是否是明文基本没啥关系。我们可以拿小厂商的ftp来练手,此时我们还需要一个工具1ftpfuzzer,fuzz即为暴力,打过信息学联赛的朋友们大概一定会很痛恨一种东西,强数据,明明样例数据能过,确总有好几个测试点过不去,而在acm中,一个点不过就0分,我也是想骂人。。。咳咳,回到fuzz上来,fuzz会暴力模拟上万种奇怪的,强数据来测试,我们可以通过ftpfuzzer来完成,设置好基本参数后,我们只需要喝喝红花茶等等就好了,如果顺利,很快就会fuzz结束,因为有测试数据成功了,我们可以在ftpfuzzer的工作栏中找到发生溢出的数据,然后如上的本地溢出进行测试,流程基本一致,只是在溢出工作上,我们总不能用ftpfuzzer来攻击把?我们此时可以吧设计好的数据存在一个数组中。。。
然后可以用编程语言来实现发送的目的。。。这个时候py最合适了。。。当然我更希望大家使用c。。。
通过winsock的api,我们可以实现发包的目的,来发动远程溢出攻击。。。至于为何没有图??大概是我们机房这边网络不稳定。。。我也快醉了。。。上午还好好的。。。如果需要图的话,我的博客里有简略的文章,里面有图,当然那个写的非常简略。。。当然希望我以后还能继续本篇的内容,写出更好的文章来。
博客地址 maxwheat.ml

谢谢大家观看

渗透测试 溢出分析套路1ST

希望正在钻研这一块的朋友看到我的文章可以带来更多的启发。

首先我们尝试一下几个基本的容易溢出的函数,首先,memcpy荣登榜首。测试代码如下。

#include”stdio.h”
#include”string.h”
main()
{
int i;
char a[4]=”s”,b[20]=”ssssssssssssssssss”;
i=sizeof(b);
memcpy(a,b,i);
printf(“a=%s\nb=%s”,a,b);
return 0;
}

这里可以看到b已经把a给覆盖了,发生了溢出,下面开始分析。

ollyjkr载入,ctrl g搜索memcpy函数,f2下断

1

然后f9跑起来,2

来到这里,继续f9(可能多次),会运行到我们设置的断点处。

这个时候ctrl f9,跑完这个函数处,可能不会直接跑到retn处,下面手动处理,f8忽略call单步,跑到retn处3

retn语句执行后,将会运行到调用的下一行,此时我们开始分析。

ESP:寄存器之一,一般情况下你拿他存个数也没啥问题,但是在运行到retn处时,esp内存储的为函数返回地址,但如果发生了溢出,多余的数据将会覆盖返回地址。。。

此时我们看下ESPes9

存储的内存地址为0018FF4C

我们再看一下这个0018FF4C内存着啥。

73737373,这不是SSSS的十六进制形式吗,果然溢出了,但如果恰巧覆盖的内容是shellcode呢?这不就是溢出攻击吗?zjo

剩下的我们计算73的个数。。。算出需要多少个字符会导致溢出。。。然后我们就可以愉快的填sh了,当然还要算上偏移,因为程序崩溃时内存会发生变动

且听下集分晓。

转载请声明来源。