2018 ICPC Asia Jakarta Regional Contest
A Edit Distance
题目链接
题意：对于一个字符串S,可以选择插入一个字母、删除一个字母、替换一个字母，将字符串S通过以上步骤变换为字符串T，其最小步骤数为edit(S,T)。求对于字符串S，编辑为相同长度的字符串T且满足edit(S,T)要大于S的长度除于2。
思路：考虑将01字符串中满足大于等于1半的字符翻转。最差情况字符串edit(S,T)==|S|/2。即0字符和1字符个数相同，根据首字符元素，选择另一个字符翻转，再将首字符翻转。满足题目要求条件。
翻转首字符意味不能通过头尾拼接得到。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 3;
int a[maxn];
char s[maxn];
int main() {
scanf("%s", s);
int len = strlen(s);
int num[2] = { 0 };
for (int i = 0; i < len; i++) {
num[s[i] - '0']++;
}
if (num[0] < num[1]) {
for (int i = 0; i < len; i++) {
if (s[i] == '1') {
s[i] = '0';
}
}
}
else if(num[0] > num[1]) {
for (int i = 0; i < len; i++) {
if (s[i] != '1') {
s[i] = '1';
}
}
}else {
int fg = 0;
for (int i = 0; i < len; i++) {
s[i] = s[0];
}
s[0] = (!(s[0] - '0')) + '0';
}
printf("%s\n", s);
} D Icy Land
题目链接
题意：给出一个R*C的图，图中#为普通地面，.为冰面，人在冰面会沿方向一直滑，在普通地面和边界才会停止。只有停止的地面才会被记录，求人在整个图都能停下被记录需要更改几个冰面变为普通地面。
思路：对于除边界内部需要每个地面都为普通地面才可以全被记录，而边界需要至少存在一个普通地面使得人在边界能停止。特判1、2情况。
#include<bits/stdc++.h>
using namespace std;
char mp[502][502];
int main(){
int r, c, i, j, ans = 0, flag = 1;
scanf("%d %d",&r,&c);
for(i = 0;i < r;i++){
scanf("%s",mp[i]);
}
if(r == 1&&c == 1){
puts("0");
}
else if(r == 1){
ans = 0;
for(i = 1;i < c - 1;i++){
if(mp[0][i] == '.'){
ans++;
}
}
printf("%d\n",ans);
}
else if(c == 1){
ans = 0;
for(i = 1;i < r - 1;i++){
if(mp[i][0] == '.'){
ans++;
}
}
printf("%d\n",ans);
}
else if(r == 2){
ans = 0;
for(i = 1;i < c - 1;i++){
if(mp[0][i] == '.'&&mp[1][i] == '.'){
ans++;
}
}
printf("%d\n",ans);
}
else if(c == 2){
ans = 0;
for(i = 1;i < r - 1;i++){
if(mp[i][0] == '.'&&mp[i][1] == '.'){
ans++;
}
}
printf("%d\n",ans);
}
else{
for(i = 1;i < r - 1;i++){
for(j = 1;j < c - 1;j++){
if(mp[i][j] != '#'){
ans++;
}
}
}
for(i = 1;i < c - 1;i++){
if(mp[0][i] == '#'||mp[r - 1][i] == '#'){
flag = 0;
}
}
for(i = 1;i < r - 1;i++){
if(mp[i][0] == '#'||mp[i][c - 1] == '#'){
flag = 0;
}
}
printf("%d\n",ans + flag);
}
return 0;
} G Go Make It Complete
题目链接
题意：对于给定的无向图，你可以选择两个满足度数和大于等于k且不相连的点连接。求图变为完全图需要的最大的k。
思路：显然k具有单调性，容易想到二分。已知k，我们可以n^2枚举两个端点，存入数据结构中，连接边并更改度数。时间复杂度n^3*logn。理论不行，但可以莽过。。
#include <bits/stdc++.h>
#define maxn 505
using namespace std;
int n,m;
int deg[maxn];
int Deg[maxn];
int g[maxn][maxn];
int G[maxn][maxn];
struct node{
int u,v;
int val;
};
bool check(int x){
memset(g,0,sizeof g);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
g[i][j]=G[i][j];
}
}
for(int i=1;i<=n;i++){
deg[i]=Deg[i];
}
while(1){
vector <node>vc;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(!g[i][j]){
vc.push_back((node){i,j,deg[i]+deg[j]});
}
}
}
int flag=0;
for(int i=0;i<vc.size();i++){
if(vc[i].val>=x)
{
deg[vc[i].u]++;
deg[vc[i].v]++;
g[vc[i].u][vc[i].v]=g[vc[i].v][vc[i].u]=1;
flag=1;
}
}
if(!flag)break;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(!g[i][j])
return 0;
}
}
return 1;
}
void input(){
scanf("%d%d",&n,&m);
for(int i=1,u,v;i<=m;i++){
scanf("%d%d",&u,&v);
Deg[u]++;
Deg[v]++;
G[u][v]=G[v][u]=1;
}
}
void solve(){
int l=0,r=1000;
int ans;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)){
ans=mid;
l=mid+1;
}
else
r=mid;
}
printf("%d\n",ans);
}
int main(){
input();
solve();
}
/*
7 5
1 2
2 3
3 4
4 1
2 4
*/ H Lexical Sign Sequence
题目链接
题意：一个字符串，将字符串中为0的可以置为1或者-1，满足接下来k个[L,R]区间内的值和大于等于val。并要求最终字典序最小。
思路：字符串先全部位置为0的置为1。从1到n贪心，用优先队列或set存对于当前i来说的包含i的区间[l,r]中的最值。临时变量t用于赋给当前区间进入时一个基准(?)。可以判定在此区间可以减去最多的次数。时间复杂度严格O(nlogn)。
网上还有区间排序后遍历区间贪心，之前想时间复杂度不对，是卡数据莽过，后来想想好像更改的次数是确定的，可能也可以。但贪心改正确性可能也有问题(?)
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n, k;
int a[maxn];
int book[maxn];
int presum[maxn];
struct SEG{
int l, r;
int sum;
bool operator <(const SEG temp)const{
return sum < temp.sum;
}
} seg[maxn];
bool cmp(SEG a,SEG b){
if(a.l!=b.l)
return a.l < b.l;
return a.r < b.r;
}
priority_queue<SEG> q;
void solve(){
int ind = 1;
int t = 0;
for (int i = 1;i<=n;i++){
while(!q.empty()&&q.top().r<i)
q.pop();
for (; ind <= k && seg[ind].l <= i;ind++){
seg[ind].sum += t;
q.push(seg[ind]);
}
if(!book[i]){
if(q.empty()||q.top().sum+2<=t){
a[i] = -1;
t-=2;
}
}
}
for (int i = 1; i <= n;i++)
printf("%d ", a[i]);
}
void input(){
scanf("%d%d", &n, &k);
for (int i = 1;i<=n;i++){
scanf("%d", &a[i]);
if(a[i]==0)
a[i] = 1;
else
book[i] = 1;
presum[i] = presum[i - 1] + a[i];
}
for (int i = 1; i <= k;i++){
scanf("%d%d%d", &seg[i].l, &seg[i].r, &seg[i].sum);
seg[i].sum -= presum[seg[i].r] - presum[seg[i].l - 1];
}
for (int i = 1; i <= k;i++){
if(seg[i].sum>0){
printf("Impossible\n");
return;
}
}
sort(seg+1,seg+1+k,cmp);
solve();
}
int main(){
input();
return 0;
}
/*
3 2
0 0 0
1 2 2
2 3 -1
*/ I Lie Detector
题目链接
题意：给出n个字符串，第i个字符串代表第i-1个字符串的真假，判定第一个字符串的真假。
思路：递推
#include<iostream>
#include<cstdio>
using namespace std;
char ch[1002];
int main(void){
int ans = 0, t;
scanf("%d",&t);
while(t--){
scanf("%s",ch);
if(ch[0] != 'T'){
ans ^= 1;
}
}
if(!ans){
puts("TRUTH");
}
else{
puts("LIE");
}
return 0;
} J Future Generation
题目链接
题意：给定n个字符串，要求寻找n个子串，满足子串递增，且所有子串长度和最大
思路：dp
#include<bits/stdc++.h>
using namespace std;
const int maxn = 7e4 + 3;
char s[maxn];
struct node {
string str;
int len;
}dat[16][maxn];
int str_cnt[16];
int dp[16][maxn];//
int n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s);
int le = strlen(s);
int lim = 1 << le;
str_cnt[i] = lim - 1;
for (int j = 1; j < lim; j++) {
string ans = "";
int cnt = 0;
for (int k = 0; k <= le - 1; k++) {
if (j&(1 << k)) {
ans += s[k];
cnt++;
}
}
dat[i][j].str = ans;
dat[i][j].len = cnt;
//cout << ans << "yyy" << endl;
}
sort(dat[i] + 1, dat[i] + lim, [&](node a, node b) {
return a.str < b.str;
});
}
int fg = 0;
for (int i = 2; i <= n; i++) {
int ptr1 = 1;//last
int ptr2 = 1;//NOw
while (i != 2 && !dp[i - 1][ptr1]) {
ptr1++;
}
for (; ptr1 <= str_cnt[i - 1]; ptr1++) {
for (; ptr2 <= str_cnt[i];) {
if (dat[i - 1][ptr1].str >= dat[i][ptr2].str) {
ptr2++;
}
else {
break;
}
}
if (ptr2 <= str_cnt[i]) {
dp[i][ptr2] = max(dp[i][ptr2], dp[i - 1][ptr1] + dat[i - 1][ptr1].len);
}
}
for (int j = 1; j <= str_cnt[i]; j++) {
dp[i][j] = max(dp[i][j], dp[i][j - 1]);
//cout << i << " " << j << " : " << dp[i][j] << endl;
}
if (!dp[i][str_cnt[i]]) {
fg = 1;
break;
}
}
if (fg)puts("-1");
else {
int ans = 0;
for (int i = 1; i <= str_cnt[n]; i++) {
//cout << dp[n][i] << " " << endl;
ans = max(ans, dp[n][i] + dat[n][i].len);
}
printf("%d\n", ans);
}
}
/*
3
aaa
aaa
aa
*/ L Binary String
题目链接
题意：对于一个01串，问最小删多少个字符可以满足01组成的二进制小于等于k
思路：贪心
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 3;
#define ll long long
ll num[102];
char ch[102];
ll wei = 0, a, len;
bool check(){
int flag = 0,i, now = 0, s = 0;
for(i = 0;i < len;i++){
if(flag){
now++;
}
else{
if(num[now]){
if(ch[i] == '0'){
flag = 1;
}
now++;
}
else{
if(ch[i] == '0'){
now++;
}
}
}
if(now == wei){
return true;
}
}
now = flag = s = 0;
for(i = 0;i < wei;i++){
if(num[i]){
now++;
}
else{
s++;
}
if(now == 2){
flag = i;
break;
}
}
now = 0;
for(i = 0;i < len;i++){
if(ch[i] == '0'){
now++;
}
if(now == s + 1){
if(len - i - 1>= wei - flag - 1){
return true;
}
break;
}
}
return false;
}
int main() {
int i;
scanf("%lld %s",&a, ch);
len = strlen(ch);
if(!a){
wei = 1;
num[0] = 0;
}
else{
while(a){
num[wei++] = a % 2;
a /= 2;
}
for(i = 0;i < wei / 2;i++){
num[i] += num[wei- i - 1];
num[wei - i - 1] = num[i] - num[wei - i - 1];
num[i] -= num[wei - i - 1];
}
}
if(wei > len){
puts("0");
}
else if(check()){
printf("%lld\n",len - wei);
}
else{
printf("%lld\n",len - wei + 1);
}
}
京公网安备 11010502036488号