CodeforcesRound#798(Div.2)A-D（未完成）-创新互联
3
6 4 2
aaaaaa
bbbb
5 9 3
caaca
bedededeb
7 7 1
noskill
wxhtzdyaabaabaa
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;
}
} 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)
4
3
1 2 3
5
2 3 4 5 1
4
2 3 1 4
1
12 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
题面
样例输入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
样例解释
官方题解
官方代码#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://azwzsj.com/article/djodpj.html
