3
6 4 2
aaaaaa
bbbb
5 9 3
caaca
bedededeb
7 7 1
noskill
wxhtzdy
样例输出aabaabaa
aaabbcc
dihktlwlxnyoz
样例解释#includeusing namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t; cin>>t;
while (t--)
{
int n,m,k; cin>>n>>m>>k;
string a,b,c; cin>>a>>b;
sort(a.begin(),a.end(),greater());
sort(b.begin(),b.end(),greater());
int ak=0,bk=0;
while (!a.empty() && !b.empty())
{
bool gde=b.back()
题意给定a,b两个字符串,长度分别为n,m,不会有某个字符既在a中又在b中。同时给你一个整数k。你可以每次在a或b中取出一个字母放入c中,直到其中至少一个字符串为空。要求不能连续在同一个字符串中连续选取k个字母。输出所有选择中,字典序最小的结果。
题解为了使字典序最小,首先将a,b内部进行排序,这样每次我们可以直接取出a,b各自最小的字符,将他们进行比较,将小的那一个字符取出放入c中即可。注意,如果在某个字符串中已经连续取k个了,就需要换一个字符串取。那就统计一下目前位置已经连续在哪个字符串中取了几次就可以了。所以在a中取字符的条件是:a剩下的最小字符比b的小,并且没有在a中连续取k次。否则就在b中取。(注意a,b两字符串之间没有相同元素,内部可能有)
代码 C++, O ( n + m ) O(n+m) O(n+m)#includeusing namespace std;
#define int long long
signed main()
{
int T;
cin >>T;
while(T --)
{
int n, m, k;
cin >>n >>m >>k;
string a, b;
cin >>a >>b;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int i = 0, j = 0, cnt = 0, t = -1;
string c;
while(i< n && j< m)
{
if(a[i]< b[j] && !(t == 0 && cnt == k) || a[i] >b[j] && t == 1 && cnt == k)
{
if(t == 1) cnt = 1;
else cnt ++;
t = 0;
c += a[i ++];
}
else
{
if(t == 0) cnt = 1;
else cnt ++;
t = 1;
c += b[j ++];
}
}
cout<< c<< endl;
}
}
pypy3,
O
(
n
+
m
)
O(n+m)
O(n+m)T = int(input())
for u in range(T):
n, m, k = map(int, input().split())
a = input()
b = input()
a = ''.join(sorted(a))
b = ''.join(sorted(b))
c = ""
cnta = cntb = i = j = 0
while i< n and j< m:
if cnta< k and a[i]< b[j] or cntb == k:
cnta += 1
cntb = 0
c += a[i]
i += 1
else:
cntb += 1
cnta = 0
c += b[j]
j += 1
print(c)
B
题面4
3
1 2 3
5
2 3 4 5 1
4
2 3 1 4
1
1
样例输出2 3 1
1 2 3 4 5
1 2 4 3
-1
样例解释## 官方题解
#includeusing namespace std;
bool took[1005];
int p[1005];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t; cin>>t;
while (t--)
{
int n; cin>>n;
for (int i=1;i<=n;i++) cin>>p[i];
for (int i=1;i<=n;i++) took[i]=0;
if (n==1)
{
cout<<"-1\n";
continue;
}
for (int i=1;i<=n-2;i++)
{
int k=1;
while (took[k] || k==p[i]) ++k;
cout<C++ Code (O(n) solution)#includeusing namespace std;
int t,n,A[1010],B[1010];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d",&A[i]);
B[i] = i;
}
if(n==1)
{
printf("-1\n");
continue;
}
for(int i=1; i
题意给定一个排列A,请你给出一个新的排列B,使A,B任何位置不相等,也就是对于任何i,A[i]!=B[i]。要求输出字典序最小的B。
题解1这题n很小,可以用
O
(
n
2
)
O(n^2)
O(n2)复杂度做。如果只有一个数字,那么A[1]==B[1],此题无解,否则有解。对于前n-2个数,只需要选择该位置能选择的最小的数:对于B[i],未在B[1]~B[i-1]出现且不等于A[i]的数中最小的一个,这样的做法可以让前n-2个数是字典序最小的。最后两个数也一定可以找到字典序最小的排列,即尝试先小后大,如果会导致A[i]==B[i],那么先大后小即可。
代码1
C++,
O
(
n
2
)
O(n^2)
O(n2)#includeusing namespace std;
#define int long long
signed main()
{
int T;
cin >>T;
while(T --)
{
int n;
cin >>n;
vectora(n + 1), b(1, 0), st(n + 1, 0);
for(int i = 1; i<= n; i ++)
cin >>a[i];
if(n == 1)
{
cout<< -1<< endl;
continue;
}
for(int i = 1; i<= n - 2; i ++)
{
for(int j = 1; j<= n; j ++)
if(!st[j] && j != a[i])
{
b.push_back(j);
st[j] = 1;
break;
}
}
for(int i = 1; i<= n; i ++)
if(!st[i])
b.push_back(i);
if(a[n - 1] == b[n - 1] || a[n] == b[n])
swap(b[n - 1], b[n]);
for(int i = 1; i<= n; i ++)
cout<< b[i]<< ' ';
cout<< endl;
}
}
题解2当n==1时,无解,否则有解。因此,在前n-2个数选取完毕后,最后2个数必定有解。首先将b赋值为1:n,此为字典序最小的排列。然后考虑a,k从1到n-2交换,假设前k-1个数已经为字典序最小,而a[k]==b[k],只需要将b[k]与b[k+1]交换,则可以保证前k个数字典序最小,证明:因为之前所有交换都发生在b[1~k]之间,所以b[k+1~n]仍然有序,b[k]<=k<=min(b[k+1~n]),所以在min(b[k~n])=b[k],若要保证a[k]!=b[k],则b[k]需要与后面的数交换,为使字典序最小,则交换后面最小的数,即b[k+1]。如此则保证了前k个数字典序最小。而最后两个数只需要保证不与a对应位置相等即可。
代码2
pypy3,
O
(
n
)
O(n)
O(n)T = int(input())
for _ in range(T):
n = int(input())
a = list(map(int, input().split()))
b = sorted(a)
if n == 1:
print(-1)
continue
for i in range(n - 1):
if a[i] == b[i]:
b[i], b[i + 1] = b[i + 1], b[i]
if a[-1] == b[-1]:
b[-1], b[-2] = b[-2], b[-1]
print(" ".join(map(str, b)))
C
题面![在这里插入图片描述](/upload/otherpic12/a10a907c85804d5f96dc242a9505d62c.jpg)
![在这里插入图片描述](/upload/otherpic12/521be20efa114171915bf12b0c00a725.jpg)
样例输入4
2
1 2
4
1 2
2 3
2 4
7
1 2
1 5
2 3
2 4
5 6
5 7
15
1 2
2 3
3 4
4 5
4 6
3 7
2 8
1 9
9 10
9 11
10 12
10 13
11 14
11 15
样例输出0
2
2
10
样例解释![在这里插入图片描述](/upload/otherpic12/00baa23a069e4ebc87335bb44f778118.jpg)
官方题解![在这里插入图片描述](/upload/otherpic12/94e01155e56e4e0da557d7e9c65a1497.jpg)
![在这里插入图片描述](/upload/otherpic12/a283b7d250394eea88d4edea4e888f2a.jpg)
官方代码#includeusing namespace std;
vector>g(300005);
int ch[300005],dp[300005];
void dfs(int p, int q)
{
ch[p]=1,dp[p]=0; int s=0;
for (auto it : g[p]) if (it!=q)
{
dfs(it,p); s+=dp[it];
ch[p]+=ch[it];
}
for (auto it : g[p]) if (it!=q)
{
dp[p]=max(dp[p],s-dp[it]+ch[it]-1);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t; cin>>t;
while (t--)
{
int n; cin>>n;
for (int i=1;i<=n;i++) g[i].clear();
for (int i=1;i>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
cout<
题意给你一棵树,根节点为1,根节点的度不大于2,其他节点的度不大于3。首先根节点被感染了,并且每次迭代,感染的节点会像相邻节点扩散一个单位。在每次迭代前,你可以删掉一个节点,那么就不能通过这个节点扩散了,那么可能可以救下一些节点,问你最多能救下多少个节点。
题解- 总节点数=救下的节点数+删除的节点数+感染的节点数。
- 这是一棵有根树。
- 如果在感染t前删掉t节点,则能救下t节点的所有子孙节点。
- 我们考虑感染t:
a. 如果t没有孩子节点,则删不删t没有区别。
b. 如果t有一个孩子节点,则删t能救下最多节点。
c. 如果t有两个孩子节点,则必定删除一个感染一个,选择能救下最多的方式。 - 因为每次可以删除一个节点,可以保证每次只感染一个节点。
- 我们对t定义两个变量:如果感染t,能救下的节点数;如果删除t,能救下的节点数。
- 答案为:如果感染1,能救下的节点数。
代码
C++,
O
(
n
)
O(n)
O(n)#includeusing namespace std;
#define int long long
vectorh[300010], st;
pairdfs(int x)
{
vector>children;
for(auto & y : h[x])
if(!st[y])
{
st[y] = 1;
children.push_back(dfs(y));
}
if(!children.size()) return {0, 0};
else if(children.size() == 1) return{children[0].second, children[0].second + 1};
else return {max(children[0].first + children[1].second, children[0].second + children[1].first),
2 + children[0].second + children[1].second};
}
signed main()
{
int T;
cin >>T;
while(T --)
{
int n;
cin >>n;
st = vector(n + 1, 0);
for(int i = 1; i<= n; i ++)
h[i] = vector(0);
for(int i = 1; i< n; i ++)
{
int u, v;
cin >>u >>v;
h[u].push_back(v);
h[v].push_back(u);
}
st[1] = 1;
cout<< dfs(1).first<< endl;
}
}
pypy3,
O
(
n
)
O(n)
O(n)
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网页标题:CodeforcesRound#798(Div.2)A-D(未完成)-创新互联
本文网址:http://cdkjz.cn/article/djodpj.html