【A】水题，把x1,x2,x3排序之后，答案就是x2-x1。
【B】水题，模拟一下就好。
【复杂度】O(len)
【代码君】
//
//Created by just_sort 2016/10/3 18:45
//Copyright (c) 2016 just_sort.All Rights Reserved
//
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
string s1[300];
string s2[300];
int main()
{
int n;
cin>>n;
string s;
cin>>s;
int cnt1 = 0,cnt2 = 0;
string temp = "";
bool flag = 0;
for(int i = 0; s[i]; i++){
if(s[i] == '_'){
if(temp=="") continue;
if(flag) s2[cnt2++] = temp;
else s1[cnt1++] = temp;
temp="";
}
else if(s[i] == '('){
if(temp=="") {
flag = 1;
continue;
}
if(flag) s2[cnt2++] = temp;
else s1[cnt1++] = temp;
temp = "";
flag = 1;
}
else if(s[i] == ')')
{
if(temp=="") {
flag = 0;
continue;}
if(flag) s2[cnt2++] = temp;
else s1[cnt1++] = temp;
temp = "";
flag = 0;
}
else temp+=s[i];
}
if(temp!=""){
if(flag) s2[cnt2++] = temp;
else s1[cnt1++] = temp;
}
int ans1 = 0;
for(int i = 0; i <cnt1; i++){
ans1 = max(ans1,(int)s1[i].size());
}
printf("%d %d\n",ans1,cnt2);
}【C】有一个序列a1,a2,…,an,现在定义bj表示数j在序列中出现的次数。问最小值bj(1≤j≤m)的最大可能值为多少,以及最少需要替换序列中的几个数?并输出替换之后的序列a1,a2,…,an。
【解题方法】贪心，过程如下：因为bj表示数j(1≤j≤m)在序列中出现的次数。而每个数出现的次数一开始是不一定的,这时候会存在一个最小值bj,即出现次数最少的那个数的出现次数。而这个最大可能值的含义是我们要替换一些数,使得出现次数最少的次数尽可能大。例如下面这组数据：
6 5
1 2 2 345 2134 885
最开始bj(1≤j≤m)分别为：
j= 1 2 3 4 5
bj= 1 2 0 0 0
那此时bj最小值为0,为了使bj最小值尽可能大,我们需做如下替换:
2->3 345->4 2134->5
这样之后bj最小值为1,替换次数为3。由抽屉原理可知,bj最小值的最大可能值为n/m。而要使得bj(1≤j≤m)均达到n/m,那就必须将>m的数或是bj>n/m的数替换成bj<n/m的数。按照这个过程贪心就好了。
【代码君】//
//Created by just_sort 2016/9/12 16:50
//Copyright (c) 2016 just_sort.All Rights Reserved
//
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 2222;
int a[maxn],b[maxn];
int n,m;
int main()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
cin>>a[i];
if(a[i] <= m) b[a[i]]++;
}
int cnt = 0;
for(int i = 1, j = 1; i <= n; i++)
{
while(j <= m && b[j] >= n / m) j++;
if(j > m) break;
if(a[i] > m || b[a[i]] > n / m)
{
if(a[i] <= m) b[a[i]]--;
a[i] = j, b[j]++,cnt++;
}
}
cout<<n/m<<" "<<cnt<<endl;
for(int i = 1; i <= n; i++)
{
cout<<a[i]<<" ";
}
}【D】给你一个n/*m的矩阵，然后你们有不少于k条河流，然后你需要使得一些河流变成陆地，使得河流的数量恰好等于k，问你至少填多少个水。河流的定义是水塘，且不与外界相连的地方。
【解题方法】直接dfs搜出每一条河流，然后贪心排序，从小到大去填满就好了。
【代码君】
//
//Created by just_sort 2016/9/12 16:50
//Copyright (c) 2016 just_sort.All Rights Reserved
//
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 55;
const int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}};
int n,m,k;
char s[maxn][maxn];
int vis[maxn][maxn];
int area,flag,cnt;
void dfs1(int x,int y)
{
area++;
vis[x][y] = 1;
if(x == 0 || x == n-1 || y == 0 || y == m-1) flag = 1;
for(int i = 0; i < 4; i++)
{
int dx = x + dir[i][0];
int dy = y + dir[i][1];
if(dx < 0 || dx >= n) continue;
if(dy < 0 || dy >= m) continue;
if(s[dx][dy] == '*') continue;
if(vis[dx][dy]) continue;
dfs1(dx,dy);
}
}
void dfs2(int x,int y)
{
s[x][y] = '*';
for(int i = 0; i < 4; i++)
{
int dx = x + dir[i][0];
int dy = y + dir[i][1];
if(dx < 0 || dx >= n) continue;
if(dy < 0 || dy >= m) continue;
if(s[dx][dy] == '*') continue;
dfs2(dx,dy);
}
}
struct node{
int a,b,c;
bool operator<(const node &rhs) const{
return a < rhs.a;
}
}t[5000];
int main()
{
cin>>n>>m>>k;
for(int i = 0; i < n; i++) cin>>s[i];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(!vis[i][j] && s[i][j] == '.'){
area = 0;
flag = 0;
dfs1(i,j);
if(flag == 1) continue;
t[cnt].a = area,t[cnt].b = i,t[cnt].c = j;
cnt++;
}
}
}
sort(t,t+cnt);
int ans = 0;
for(int i = 0; i < cnt - k; i++){
ans += t[i].a;
dfs2(t[i].b,t[i].c);
}
cout<<ans<<endl;
for(int i = 0; i < n; i++){
cout<<s[i]<<endl;
}
}【E】给你一个无向图，然后让你给边定向，使得入度等于出度的点最多。
【解题方法】考虑欧拉图，只要所有点的度数为偶数就可以了。那么答案就是奇数度数的点集，然后我们不停的dfs，把欧拉路都画出来就行了。
【代码君】
//
//Created by just_sort 2016/9/12 16:50
//Copyright (c) 2016 just_sort.All Rights Reserved
//
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 222;
set <int> g[maxn];
vector<pair<int,int> >ans;
int n,m,degree[maxn];
void init(){
memset(degree,0,sizeof(degree));
for(int i = 0; i < maxn; i++) g[i].clear();
ans.clear();
}
void dfs(int u){
while(g[u].size()){
int v = *g[u].begin();
g[u].erase(v);g[v].erase(u);
if(u != n+1 && v != n+1) cout<<u<<" "<<v<<endl;
dfs(v);
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
init();
cin>>n>>m;
while(m--){
int u,v;
cin>>u>>v;
g[u].insert(v);
g[v].insert(u);
degree[u]++,degree[v]++;
}
int sum = 0;
for(int i = 1; i <= n; i++){
if(degree[i]&1){
sum++,g[i].insert(n+1),g[n+1].insert(i);
}
}
cout<<n-sum<<endl;
for(int i = 1; i <= n; i++) dfs(i);
}
return 0;
}
【F】留坑待填
京公网安备 11010502036488号