|
Table of Contents
codeforces----1015
codeforces----1015A
codeforces----1015B
codeforces----1015C
codeforces----1015D
codeforces----1015E
codeforces----1015F
codeforces----1015
codeforces----1015A
http://codeforces.com/problemset/problem/1015/A
给定多个区间，输出没有在给定区间的数值。
数据范围极小直接暴力即可，若数据较大应该使用离散化处理
#include<iostream>
#include<cstring>
using namespace std;
int main() {
int n, m;
while ( cin >> n >> m ) {
bool ans[104];
memset ( ans, 0, sizeof ans );
while ( n-- ) {
int temp1, temp2;
cin >> temp1 >> temp2;
while ( temp1 <= temp2 )
ans[temp1++] = true;
}
int flag = 0;
for ( int i = 1; i <= m; i++ )
if ( ans[i] == false ) flag++;
cout << flag << endl;
for ( int i = 1; i <= m; i++ )
if ( ans[i] == false ) cout << i << ' ';
cout << endl;
}
return 0;
}
codeforces----1015B
http://codeforces.com/problemset/problem/1015/B
问a串在多少次变换后变到b串。数据较小，由冒泡排序直接模拟即可
#include<cstring>
#include<iostream>
using namespace std;
int main() {
int n;
while ( cin >> n ) {
char s1[52], s2[52];
cin >> s1 >> s2;
int flag = 0, ans[200008];
for ( int i = 0; i < n; i++ ) {
for ( int j = i; j < n; j++ )
if ( s1[j] == s2[i] ) {
while ( j > i ) {
swap ( s1[j], s1[j - 1] );
ans[flag++] = j--;
}
break;
}
if ( s1[i] != s2[i] ) break;
}
if ( strcmp ( s1, s2 ) == 0 ) {
cout << flag << endl;
for ( int i = 0; i < flag; i++ )
cout << ans[i] << ' ';
cout << endl;
} else cout << "-1" << endl;
}
return 0;
}
codeforces----1015C
问买东西的时候最少买多少件打折物品，可以买下所有商品。
根据打折前后的差运算即可。
#include<cstring>
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
long long sum;
priority_queue<int, vector<int>, greater<int> >*que;
void build() {
int a, b;
scanf ( "%d%d", &a, &b );
sum += a;
que->push ( b - a );
}
int main() {
int n, m;
while ( ~scanf ( "%d%d", &n, &m ) ) {
que = new priority_queue<int, vector<int>, greater<int> >;
sum = 0;
while ( n-- ) build();
int ans = 0;
while ( !que->empty() )
if ( sum <= m ) break;
else {
ans++;
sum += que->top();
que->pop();
}
if ( sum <= m ) cout << ans << endl;
else cout << "-1" << endl;
delete que;
}
return 0;
}
codeforces----1015D
http://codeforces.com/problemset/problem/1015/D
在k次变换后恰好进行s次移动。
注意输出 NO 的情况。
#include<cstring>
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
int main() {
long long n, m, k;
while ( cin >> n >> m >> k ) {
if ( ( n - 1 ) *m < k || m > k ) {
cout << "NO" << endl;
continue;
}
cout << "YES" << endl;
int Now = 1;
k -= m;
while ( m-- ) {
if ( k >= n - 2 ) {
k -= n - 2;
if ( Now == 1 ) Now = n;
else Now = 1;
} else if ( k > 0 ) {
if ( Now == 1 ) Now = 1 + 1 + k;
else Now = n - ( 1 + k );
k = 0;
} else {
if ( Now == n ) Now = n - 1;
else Now++;
}
cout << Now << ' ';
}
cout << endl;
}
return 0;
}
codeforces----1015E
http://codeforces.com/problemset/problem/1015/E2
将一张图的一种可能的星星分布位置列出来。
直接模拟即可，E1和E2题目相同，数据范围不同。
#include<cstring>
#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
int ma[1008][1008];
int ans[1000008][3];
int main() {
int n, m;
char in[1008];
while ( ~scanf ( "%d%d", &n, &m ) ) {
memset ( ma, 0, sizeof ma );
for ( int i = 1; i <= n; i++ ) {
scanf ( "%s", in );
for ( int j = 1; j <= m; j++ )
if ( in[j - 1] == '*' )
ma[i][j] = 2;
}
int flag = 0;
for ( int i = 1; i <= n; i++ )
for ( int j = 1; j <= m; j++ )
if ( ma[i][j] != 0 ) {
int k = 0;
while ( ++k ) {
if ( ma[i - k][j] != 0 && ma[i][j - k] != 0 && ma[i + k][j] != 0 && ma[i][j + k] != 0 )
ma[i - k][j] = ma[i][j - k] = ma[i + k][j] = ma[i][j + k] = 1;
else break;
}
if ( k > 1 ) {
ma[i][j] = 1;
ans[flag][0] = i, ans[flag][1] = j, ans[flag][2] = k - 1;
flag++;
}
}
bool vju = true;
for ( int i = 1; i <= n; i++ )
for ( int j = 1; j <= m; j++ )
if ( ma[i][j] == 2 ) {
vju = false;
break;
}
if ( !vju ) printf ( "-1\n" );
else {
printf ( "%d\n", flag );
for ( int i = 0; i < flag; i++ )
printf ( "%d %d %d\n", ans[i][0], ans[i][1], ans[i][2] );
}
}
return 0;
}
codeforces----1015F
http://codeforces.com/problemset/problem/1015/F
应该是一道dp+记忆化数组，状态转移我没有找到。。。QAQ | 
转播
