校赛低年级组解题报告,,,by五楼team

Posted by Cww97 on 2016-05-26

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/51510077
/写在最前面:
我的代码不是最优的,也许蛮丑的,,,
不过,能A,(不要在意这些细节
如果看不懂,请联系我,我再做补充
由于学校oj有点坑爹,这里就把题目贴上来了
C题和F题的代码有cdm提供
/

A:矩形面积
一条绳子,用这个绳子可以围成的最大矩形的面积是多少
题目不贴了,相信大家都秒了,,,

1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
int T,n;scanf("%d",&T);
for (;T--;){
scanf("%d",&n);
double x=n/4.0;
printf("%.2lf\n",x*x);
}
return 0;
}

Problem B: 排队买夜宵

Description
木下吉子五月二十号去食堂买夜宵,她发现了令人悲戚的一幕,食堂门口排满了人,而更让人悲戚的是每当有一个人排到队伍的末尾,如果他/她前面是异性,他们就马上牵手走人了。
给定一个序列,从前往后进入队伍的学生的性别,女生用’0’表示,男生用’1’表示,木下吉子想要知道最终队伍的长度(假设不碰到异性不会有人离开)。

Input
第一行为数据的组数T(T≤100)
每组数据有一行字符串S,为排队的序列,1≤|S|≤10^3。
Output
一行数字,最终队伍的长度。
Sample Input
2
10
110
Sample Output
0
1

弄个栈,,,注意字符串读入

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<stack>
using namespace std;
int main(){
//freopen("fuck.in","r",stdin);
//freopen("fuck.out","w",stdout);
int T,n;scanf("%d",&T);
for (;T--;){
string st;
cin>>st;
int len=st.size();
int a[1007];
for (int i=0;i<len;i++)a[i]=st[i]-'0';
//for (int i=0;i<len;i++)printf("%d",a[i]);
stack<int >s;
for (int i=0;i<len;i++){
if (s.empty()){
s.push(a[i]);
}else {
if (s.top()^a[i]==1)s.pop();
else s.push(a[i]);
}
}
printf("%d\n",s.size());
}
return 0;
}

Problem C. 数正方形
描述 木下吉子有一个n×n的方阵,元素为’.’或’_’。 木下吉子想知道有多少用’_’构成的正方形。 可以使用左上角坐标x,y以及边长a来描述正方形(a > 1) 则有gx+i,y = gx,y+i = gx+a−1,y+i = gx+i,y+a−1 =’’(0 6 i < a)
输入数据 第一行为测试数据组数T(T 6 30) 每组数据第一行为n,即矩阵的大小(1 6 n 6 1000) 接下来n行每行有n个字符,为’.’或’
’。
输出数据
给定矩阵中正方形的个数。
样例输入
2 3 *** . … 5 __** **** .. … ****
样例输出
6 29

建2000个树状数组,cdm提供的代码
(丑的不想看

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <assert.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
// head
const int N = 1000+5;

template<typename T>
struct BIT {
T t[N];
int n;

inline int lowbit(int x) {
return x&(-x);
}
void add(int x, T add) {
while (x <= n) t[x] += add, x += lowbit(x);
}
T sum(int x) {
T ans = 0;
while (x) ans += t[x], x -= lowbit(x);
return ans;
}
void init(int n) {
this->n = n;
for (int i = 0; i <= n; i++) t[i] = 0;
}
};

BIT<int> bt[N<<1];

int t, n;
char s[N][N];
int l[N][N], r[N][N], u[N][N], d[N][N];
vector<PII> bk[N];


void cal(LL &ans, int x, int y) {
int v = min(l[x][y], d[x][y]);
if (v == 0) return;
int pos = x + y;
ans += bt[pos].sum(y) - bt[pos].sum(max(y - v, 0));
}

LL solve() {
scanf("%d", &n);
assert(n >= 1 && n <= 1000);
memset(l, 0, sizeof l);
memset(r, 0, sizeof r);
memset(u, 0, sizeof u);
memset(d, 0, sizeof d);
for (int i = 1; i <= n; i++) {
bt[i].init(n);
bt[i+n].init(n);
bk[i].clear();
}

for (int i = 1; i <= n; i++) {
scanf("%s", s[i]+1);
for (int j = 1; j <= n; j++) {
assert(s[i][j] == '*' || s[i][j] == '.');
l[i][j] = s[i][j] == '*' ? l[i][j-1] + 1 : 0;
u[i][j] = s[i][j] == '*' ? u[i-1][j] + 1 : 0;
}
}
for (int i = n; i > 0; i--) {
for (int j = n; j > 0; j--) {
r[i][j] = s[i][j] == '*' ? r[i][j+1] + 1 : 0;
d[i][j] = s[i][j] == '*' ? d[i+1][j] + 1 : 0;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int ub = min(u[i][j], r[i][j]);
if (ub == 0) continue;
bk[j+ub-1].push_back(make_pair(i, j));
}
}

LL ans = 0;
for (int j = n; j > 0; j--) {
for (int i = 0; i < bk[j].size(); i++) {
int x = bk[j][i].fi, y = bk[j][i].se;
bt[x + y].add(y, 1);
}
for (int i = 1; i <= n; i++) {
cal(ans, i, j);
}
}
return ans;
}

int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &t);
while (t--) {
printf("%lld\n", solve());
}
assert(scanf("%s", s[0]) != 1);
return 0;
}

Problem D: 高年级竞赛
Description
木下吉子听说高年级竞赛三人一支队伍,规则是每个队伍中至少有两人在一个寝室。
有n个人,m个寝室,给定每个人的寝室号a_i(1≤a_i≤m),问最多能够组成多少支队伍。
需要注意的是为了公平竞争,所有队伍都得由三人组成。
Input
第一行为数据的组数T(T≤100)
每组数据第一行为n,m(1≤n,m≤10^3)
接下一行有n个数a_1…a_n(1≤a_i≤m),a_i是第i个人的寝室编号。
Output
一行数字,最多多少支队伍。
Sample Input
2
3 3
1 2 3
6 4
1 1 2 2 3 4
Sample Output
0
2

存每个寝室的人数就好了
平方暴力,,,
,写的有点蠢

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
//D 高年级组
//by cww97
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const int N=1007;
int a[N],n,m,x;

int findteammate(){
for (int j=1;j<=n;j++){
if (a[j]&1)return j;
}
for (int j=1;j<=m;j++){
if (a[j]) return j;
}
return -1;
}

int main(){

int T;scanf("%d",&T);
for (;T--;){
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
for (int i=0;i<n;i++){
scanf("%d",&x);
a[x]++;
}
int ans=0;
for (int i=1;i<=m;i++){
if (a[i]>1){
a[i]-=2;
int k=findteammate();
if (k!=-1){
a[k]--;
ans++;
}else break;
//printf("team++:%d,%d,%d\n",i,i,k);
i--;
}
}
printf("%d\n",ans);
}
return 0;
}

Problem E: 暗之高年级竞赛

Description
木下吉子听说高年级竞赛三人一支队伍,规则是每个队伍中至少有两人在一个寝室。为了增加气氛,木下吉子打算举办暗之高年级竞赛,其规则与高年级竞赛背道而驰,每个队伍的三个必须来自不同寝室。
有n个人,m个寝室,给定每个人的寝室号a_i(1≤a_i≤m),问最多能够组成多少支队伍。需要注意的是为了公平竞争,所有队伍都得由三人组成。
Input
第一行为数据的组数T(T≤100)
每组数据第一行为n,m(1≤n,m≤10^3)
接下一行有n个数a_1…a_n(1≤a_i≤m),a_i是第i个人的寝室编号。
Output
一行数字,最多多少支队伍。
Sample Input
2
3 3
1 2 3
6 4
1 1 2 2 3 4
Sample Output
1
2

大家上半学期都学过堆了,不要以为堆只能排序用这里写图片描述
优先队列,,,里面默认就是个大根堆,所以
每次取人数最多的三个寝室,然后组队
如果寝室不空,扔回堆里,没了

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
//E Dark 高年级组
//by cww97
#include<queue>
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1007;
int a[N],n,m;

int main(){
//freopen("fuck.in","r",stdin);
int T,x;scanf("%d",&T);
for (;T--;){
scanf("%d%d",&n,&m);
memset(a,0,sizeof(a));
for (int i=0;i<n;i++){
scanf("%d",&x);
a[x]++;
}
priority_queue<int>q;
while (!q.empty())q.pop();
for (int i=1;i<=m;i++)if(a[i]>0)q.push(a[i]);

int ans=0,x,y,z;
while (q.size()>=3){
x=q.top();q.pop();
y=q.top();q.pop();
z=q.top();q.pop();
//int t=min(min(x,y),z);
int t=1;
//printf("team:%d,%d,%d:%d\n",x,y,z,t);
ans+=t;
if (x-t>0)q.push(x-t);
if (y-t>0)q.push(y-t);
if (z-t>0)q.push(z-t);
//printf("%d\n",q.size());
}
printf("%d\n",ans);
}
return 0;
}

Problem H. 集合维护
描述
木下吉子有一个集合S,初始有S = ∅ 。木下吉子定义了两种集合上的操作。 第一种是交操作,表示为1 P,执行S ← STP。 第二种是并操作,表示为2 P,执行S ← SSP。 P是一个区间。木下吉子想要知道经过m次操作后S的情况。
输入数据 第一行为数据的组数T(T 6 150) 每组数据第一行为m代表对S操作的次数(m 6 100) 接下来m行按照顺序给出对集合的操作,每次操作为1 P或者2 P。 P的格式为Ll,rR其中L ∈(,[ 0 6 l,r 6 100 R ∈),] 输出数据
每组数据输出一行,表示集合的情况。 空集输出”empty set”。 如果集合中有多段,使用U(英文字母大写U)连接每段集合,代表并。 集合以最少集合的并集输出。
样例输入
4 1 1 (1,2) 2 2 (1,2) 2 (2,3) 2 2 (1,2) 2 [2,3) 3 2 [2,3] 2 [4,5] 1 (2,5)>

有点懒,题还没补,先帖cdm的代码吧,
(这一波头文件有毒= =
题目没明说全是整数,强行当成全是整数来写
那么问题就简单了,,,,开个200就行了

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <ctime>
#include <assert.h>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
// head
const int N = 205;

bool res[N];

void pRange(int l, int r) {
printf("%c%d,", l & 1 ? '(' : '[', l / 2);
printf("%d%c", (r+1) / 2, r & 1 ? ')' : ']');
}

void p() {
bool flag = false;
for (int i = 0; i < N; i++) {
if (!res[i]) continue;
int r = i;
while (res[r+1]) r++;
if (flag) putchar('U');
pRange(i, r);
flag = true;
i = r;
}
puts(flag ? "" : "empty set");
}

void join(int l, int r) {
for (int i = 0; i < l; i++) {
res[i] = false;
}
for (int i = r+1; i < N; i++) {
res[i] = false;
}
}

void uni(int l, int r) {
for (int i = l; i <= r; i++) {
res[i] = true;
}
}

char s[15];
int main() {
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
int t, n;
scanf("%d", &t);
while (t--) {
memset(res, 0, sizeof res);
assert(scanf("%d", &n) == 1);
assert(n >= 1 && n <= 100);
char lop, rop;
int l, r, op;
while (n--) {
scanf("%d %c%d,%d%c", &op, &lop, &l, &r, &rop);
assert(l >= 0 && l <= 100 && r >= 0 && r <= 100);
assert(l <= r);
l <<= 1;
r <<= 1;
if (lop == '(') l++;
if (rop == ')') r--;
if (op == 1) {
join(l, r);
} else {
uni(l, r);
}
}
p();
}
assert(scanf("%s", &s) != 1);
return 0;
}

Problem G: 线段树
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 356 Solved: 97
[Submit][Status][Web Board]
Description
最近木下吉子在学习线段树,她有一份线段树的代码,线段树中每个节点维护了一条L到R的线段,节点标号为rt,木下吉子想要知道调用st.build(1,1,n)之后会形成多少不同标号的节点。
struct SegmentTree {
void build(long long rt, long long L, long long R) {
if (L == R) {
return;
} else {
long long mid = (L + R) / 2;
build(rt * 2, L, mid);
build(rt * 2 + 1, mid+1, R);
}
}
};
SegmentTree st;
Input
第一行为数据的组数T(T≤200)
每组数据一行,为n的大小(1≤n≤10^18)
Output
一行数字,规模为n的线段树中不同节点的个数。
Sample Input
3
1
2
5
Sample Output
1
3
9

考虑一个线段树,用如上方式build
除了最底层,都是满的,我们只需统计最底层有多少个节点
有人说直接输出2n-1可A,,,这里写图片描述

我这个代码里的t为倒数第二层需要“分裂”的节点数

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
//G 线段树
//by cww97
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;

long long power(int t){
if (!t)return 1;
if (t==1)return 2;
long long tmp=power(t>>1);
tmp=tmp*tmp;
if (t&1)tmp=2*tmp;
return tmp;
}

int main(){
//freopen("fuck.in","r",stdin);
int T;scanf("%d",&T);
long long n;
for (;T--;){
cin>>n;
long long t=0;
while ((power(t))<n)t++;
long long ans=(power(t))-1;
t--;
if (ans)ans+=(n-(power(t)))*2;
else ans=1;
cout<<ans<<endl;
}
return 0;
}

Problem H: 方格取数
木下吉子有一个n*n的网格卡片,每个方格中含有一个数字。木下吉子想到了一个游戏,他想以最小代价划掉所有网格中的数字。每次在网格中没被划掉的位置中选择一个位置,然后划掉这个位置所在的行和列的所有方格,把选定位置的数字累加到代价中。同一位置可以被划掉多次,但被划掉的位置不能被选择,开始所有数字没被划掉,初始代价为0。
Input
第一行为数据的组数T(T≤100)
每组数据第一行为网格的规模n(n≤100)
接下来n行每行n个数字,a_{i,j}表示网格中i行j列的数字(1≤a_{i,j}≤10^6)
Output
一行数字,划掉所有数字的最小代价。
Sample Input
1
2
1 2
2 5
Sample Output
4

此题思远姐姐A了
这里写图片描述
天线宝宝= =

KM算法,,,,(除了这个,思远姐姐什么都没说

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
//problem H
//by xsy
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <string>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define mem(x) memset(x,0,sizeof(x))
typedef long long ll;
int TT;

const int maxn = 105;
int W[maxn][maxn],n;
int Lx[maxn],Ly[maxn];
int LEFT[maxn];
bool S[maxn],T[maxn];

bool match(int i) {
S[i] = true;
for (int j=1;j<=n;j++)
if (Lx[i]+Ly[j]==W[i][j] && !T[j]) {
T[j] = true;
if (!LEFT[j]|| match(LEFT[j])) {
LEFT[j] = i;
return true;
}
}
return false;
}

void update() {
int a = 1<<30;
for (int i=1;i<=n;i++) if (S[i])
for (int j = 1;j<=n;j++) if (!T[j])
a=min(a,Lx[i]+Ly[j] - W[i][j]);
for (int i=1;i<=n;i++) {
if (S[i]) Lx[i] -= a;
if (T[i]) Ly[i] += a;
}
}

void KM() {
for (int i=1;i<=n;i++) {
LEFT[i] = Lx[i] = Ly[i] = 0;
for (int j=1;j<=n;j++)
Lx[i] = max(Lx[i],W[i][j]);
}
for (int i=1;i<=n;i++) {
for(;;) {
for (int j=1;j<=n;j++) S[j] = T[j] = 0;
if (match(i)) break; else update();
}
}
}

int main()
{
scanf("%d",&TT);
while (TT--) {
scanf("%d",&n);
for (int i=1;i<=n;i++) for (int j=1;j<=n;j++)
{
scanf("%d",&W[i][j]);
W[i][j] = -W[i][j];
}
KM();
ll ans = 0;
for (int i=1;i<=n;i++)
ans+=Lx[i] + Ly[i];
cout << -ans <<endl;
}
return 0;
}

Problem I: 格子涂色
Description
木下吉子有一个n*n的方格,一开始所有格子都是没有涂色的。每一轮,她会随机选择所有格子中的一个点(x,y)作为左上角,并以点(n,n)为右下角,将这两个点所组成的矩形内的所有格子涂色。求经过k轮操作后涂色格子数目的期望值。
Input
第一行为测试数据的组数T(1≤T≤50)
每组测试数据有两个整数n和k(1≤n≤1000),(1≤k≤100)
Output
对于每组测试数据,输出一行结果,四舍五入保留两位小数。
Sample Input
2
5 2
2 1
Sample Output
13.16
2.25

承旭A了,,,他说很水,其他什么都没说
这里写图片描述
数学期望怎么算啊= =

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int N=1086,oo=0x3f3f3f3f;
int T,n,k;
double power(double x,int y){
double re=1;
for (;y;y/=2,x*=x)
if (y%2==1) re*=x;
return re;
}
int main(){
for (scanf("%d",&T);T--;){
scanf("%d%d",&n,&k);
double ans=n*n;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
ans-=power(1.0-(double(i*j))/n/n,k);
printf("%.2lf\n",ans);
}
return 0;
}

Problem J: 线段树++
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 154 Solved: 10
[Submit][Status][Web Board]
Description
最近木下吉子在学习线段树,她有一份线段树的代码,线段树中每个节点维护了一条L到R的线段,节点标号为rt,木下吉子想要知道调用st.build(1,1,n)之后rt的最大值。
struct SegmentTree {
void build(long long rt, long long L, long long R) {
if (L == R) {
return;
} else {
long long mid = (L + R) / 2;
build(rt * 2, L, mid);
build(rt * 2 + 1, mid+1, R);
}
}
};
SegmentTree st;
Input
第一行为数据的组数T(T≤200)
每组数据一行,为n的大小(1≤n≤10^18)
Output
一行数字,规模为n的线段树中的最大标号。
Sample Input
3
1
2
5
Sample Output
1
3
9

考虑最后一层的节点数量,,,,
1,2,4,8,16,32.。。。以此类推,像漫水一样
大家可以画画最后一层build的过程
画个5,6,7,8个节点的,基本就能脑补出来了

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
//J 线段树++
//by cww97
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;

long long power(int t){
if (t==0)return 1;
if (t==1)return 2;
long long tmp=power(t>>1);
tmp=tmp*tmp;
if (t&1)tmp=2*tmp;
return tmp;
}

int main(){
//freopen("fuck.in","r",stdin);
int T;scanf("%d",&T);
long long n;
for (;T--;){
cin>>n;
long long t=0;
while ((power(t))<n)t++;
long long ans=power(t)-1;

if (!ans)ans=1;
else {
int tag=0;
long long k=(n-power(t-1));
while (k>=power(tag)){
tag++;
t--;
ans+=power(t);
}
ans-=power(t);
ans+=2;
}
cout<<ans<<endl;
}
return 0;
}

Problem K: 软件安装
Description
木下吉子有一些软件包要安装,这些软件之间存在依赖关系,如果包x依赖包y,则y必须在x之前安装。他想知道自己能否顺利将这些软件全部成功安装。
Input
有多组测试数据,第一行一个整数T(1≤T≤20),表示测试数据的组数。对于每组测试数据:
第一行两个整数n和m,分别表示软件包的数目和依赖关系数目(1≤n≤1000,1≤m≤1000)。
接下去m行,每行两个整数x和y,表示x依赖y(1≤x,y≤n)。
Output
对于每组测试数据,如果能够全部成功安装,输出YES,否则输出NO。
Sample Input
2
3 3
1 2
2 3
3 1
3 2
1 2
2 3
Sample Output
NO
YES

承旭和思远姐姐都说拓扑排序,,,
我dfs过了,暴力出奇迹,,,
虽然也想到了topsort,为什么不写呢,因为我懒啊

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
//K Install Software
//by cww97
#include<queue>
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1007;
int a[N],n,m;
bool vis[N],ok[N];

struct Edge{
int x,y;
Edge():x(0),y(0){}
Edge(int _x,int _y){x=_x;y=_y;}
};
vector <Edge> edges;
vector <int> G[N];
vector <int> need[N];

void AddEdge(int x,int y){
need[y].push_back(x);
edges.push_back(Edge(x,y));
G[x].push_back(edges.size()-1);
}

bool check(int x){
for (int i=0;i<need[x].size();i++){
int k=need[x][i];
if (!vis[k]&&!ok[k])return 0;
}
return 1;
}

void DFS(int x){
//printf("%d->",x);
vis[x]=1;
for (int i=0;i<G[x].size();i++){
Edge e=edges[G[x][i]];
if (!vis[e.y]&&check(e.y))DFS(e.y);
}
}

int main(){
//freopen("fuck.in","r",stdin);
int T,x,y;scanf("%d",&T);
for (;T--;){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)G[i].clear();
for (int i=1;i<=n;i++)need[i].clear();
edges.clear();
memset(ok,1,sizeof(ok));
for (;m--;){
scanf("%d%d",&x,&y);
AddEdge(y,x);
ok[x]=0;
}

//for (int i=1;i<=n;i++)printf("%d ",ok[i]);puts("");
memset(vis,0,sizeof(vis));
for (int i=1;i<=n;i++){
if (!vis[i]&&ok[i])DFS(i);
}

bool flag=1;
for (int i=1;i<=n;i++)if (!vis[i]){flag=0;break;}
if (flag)puts("YES");
else puts("NO");
}
return 0;
}

Problem L: 大小写字符串
秒秒秒,,,,

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

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;

int main(){

int T,n;scanf("%d",&T);
for (;T--;){
string st1,st2;
cin>>st1>>st2;
int l1=st1.size();
int l2=st2.size();
bool ok=1;
if (l1!=l2)ok=0;
else {
int n=l1;
for (int i=0;i<n;i++){
if ('A'<=st1[i]&&st1[i]<='Z'){
st1[i]=st1[i]+'a'-'A';
}
if ('A'<=st2[i]&&st2[i]<='Z'){
st2[i]=st2[i]+'a'-'A';
}
if (st1[i]!=st2[i]){ok=0;break;}
}
}
if (ok)puts("YES");
else puts("NO");
}
return 0;
}

应他们两个要求,删掉了他们的帅照,,,,,
晚安