http://codeforces.com/contest/1506
题意：给定一个n*m的矩阵，按列依次赋值1-n*m,求该矩阵中某个位置的数x按行赋值的结果。（如图）
范围： (1≤n,m≤1e6 , 1≤x≤n?m)
转化为
样例：
输入：3 5 12
输出：14
题解：
根据数x求得其按行排列的横坐标和纵坐标，计算答案输出即可。
代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int _; 6 cin>>_; 7 while(_--) 8 { 9 long long int n,m,x; 10 cin>>n>>m>>x; 11 long long int l,r;//r代表转化后的行，l代表转化后的列 12 l=(n-1+x)/n; 13 r=(x%n==0)? n:x%n; 14 //cout<<l<<" "<<r<<endl; 15 cout<<(r-1)*m+l<<endl; 16 } 17 return 0; 18 }
题意：给定一个n的字符串,字符串包含(*和.),将*替换成x并满足以下的条件,求最少要替换多少个*。
1.第一个和最后一个*必须替换为x。
2.任意两个x之间的距离不能超过k。
范围： (1≤n,k≤50 )
样例：
输入：
5
7 3
.**.***
5 1
..*..
5 2
*.*.*
3 2
*.*
1 1
*
输出：
3
1
3
2
1
题解：
范围很小，按题意模拟暴力即可。
代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int f[100];//标记是否为x 4 int main() 5 { 6 int t; 7 cin>>t; 8 while(t--) 9 { 10 memset(f,0,sizeof f); 11 int n,k,ans=0; 12 cin>>n>>k; 13 string s; 14 cin>>s; 15 for(int i=0;i<s.size();i++)//第一个*设为x 16 { 17 if(s[i]==‘*‘) 18 { 19 f[i]=1; 20 ans++; 21 break; 22 } 23 } 24 for(int i=s.size()-1;i>=0;i--)//最后一个设为x 25 { 26 if(s[i]==‘*‘) 27 { 28 if(!f[i]) 29 { 30 f[i]=1; 31 ans++; 32 } 33 break; 34 } 35 } 36 for(int i=0;i<s.size();i++) 37 { 38 if(f[i])//如果是x 39 { 40 for(int j=i+k;j>i&&j<s.size();j--)//倒序判断 41 { 42 if(s[j]==‘*‘&&f[j]==0)//符合条件就标记 43 { 44 ans++; 45 f[j]=1; 46 break; 47 } 48 if(f[j])//如果在k范围内已经有x，直接break 49 { 50 break; 51 } 52 } 53 } 54 } 55 cout<<ans<<endl;//输出答案 56 } 57 return 0; 58 }
题意：给定两个字符串a,b，每次可以删除字符串的第一个或者最后一个字符，求使得a与b相等最少要删掉多少字符。
范围： (1≤a,b≤20)
样例：
输入：
5
a
a
abcd
bc
hello
codeforces
hello
helo
dhjakjsnasjhfksafasd
adjsnasjhfksvdafdser
输出：
0
2
13
3
20
题解：
其实就是求两个字符串的公共子串的大小，答案就是a的长度加上b的长度-两倍的最大公共子串的长度（用dp也可本人太菜不会dp）。
代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int _; 6 cin>>_; 7 while(_--) 8 { 9 int ma=0; 10 string a,b,s; 11 cin>>a>>b; 12 if(a.size()<b.size()) 13 s=a; 14 else 15 s=b; 16 for(int i=0;i<s.size();i++)//从长度小的字符串开始枚举 17 { 18 string str=""; 19 for(int j=1;j<=s.size()-i;j++)//枚举长度 20 { 21 str=s.substr(i,j);//子串 22 //cout<<str<<endl; 23 if(!(a.find(str)==string::npos)&&!(b.find(str)==string::npos))//判断该子串是否在a,b中出现过 24 { 25 ma=max(ma,int(str.size()));//记录最大长度 26 } 27 } 28 } 29 cout<<a.size()+b.size()-2*ma<<endl;//输出答案结束~ 30 } 31 return 0; 32 }
题意：给定有n个数的数组a，执行删数操作（两个数不相等就可以删除这两个数），求删完后使得数组的大小最小，并输出数组的大小。
范围：(1≤n≤2e5，1≤ai≤1e9)
样例：
输入：
5
6
1 6 1 1 4 4
2
1 2
2
1 1
5
4 5 4 5 4
6
2 3 2 1 3 1
输出：
0
0
2
1
0
题解：
贪心，每次选择总数量最多的两个数删，直到不可删为止。
代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 map<int,int> mp; 4 int main() 5 { 6 int _; 7 cin>>_; 8 while(_--) 9 { 10 mp.clear(); 11 int n,x; 12 cin>>n; 13 for(int i=0;i<n;i++) 14 { 15 cin>>x; 16 mp[x]++; 17 } 18 priority_queue<int>q;//降序 19 for(auto t:mp)//遍历每个数的个数 20 q.push(t.second); 21 while(q.size()>1) 22 { 23 int t=q.top();q.pop(); 24 int k=q.top();q.pop(); 25 t--;k--;//对最大的两个执行删除操作 26 if(t) 27 q.push(t); 28 if(k) 29 q.push(k); 30 } 31 if(q.size()) 32 cout<<q.top()<<endl; 33 else 34 cout<<0<<endl; 35 } 36 return 0; 37 }
题意：给定一个排列（1-n且数没有重复）数组q,其元素为pi,对其中每一个元素做以下操作：
qi=max(p1,p2,…,pi)
可以得到另一串数，如 [3,4,5,6,1,2] -> [3,4,5,6,6,6],现给定转化后的数组求原排列按字典序的最小的排列和最大的排列
范围： (1≤n≤2e5),(1≤qi≤n)
样例：
输入：
4
7
3 3 4 4 7 7 7
4
1 2 3 4
7
3 4 5 5 5 7 7
1
1
输出：
3 1 4 2 7 5 6
3 2 4 1 7 6 5
1 2 3 4
1 2 3 4
3 4 5 1 2 7 6
3 4 5 2 1 7 6
1
1
题解：
用并查集优化处理，用f[x]表示当前数可以填的最小数或者最大数，每次使用后更新即可。
如对于 [5,5,5,6,6,6]，处理最小：
第一个数直接写入答案，更新f[5]=f[5]+1=6;
第二个数与前一个数相等，从1开始找到一个没用过的数，把1写入答案，从当前数往下找到第一个没用过的数并更新f[find(1)]=find(f[find(1)]++)即f[1]=2;
同理把2写入答案，更新后，f[1]=3;
第四个数与前一个数不相等，直接写入答案，更新f[6]=7;
同理把3写入答案，更新后，f[1]=4;
把4写入答案，输出[5,1,2,6,3,4]。
处理最大就是更新的方向变一变，大同小异~
代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 2e5+5; 4 int ans[N],f[N],a[N]; 5 inline int find(int x)//并查集 6 { 7 return (x == f[x])? x : f[x] = find(f[x]); 8 } 9 int main() 10 { 11 int _; 12 cin >> _; 13 while( _ -- ) 14 { 15 int n; 16 cin >> n; 17 for(int i = 1 ;i <= n ; i ++ ) 18 { 19 cin >> a[i]; 20 f[i] = i;//初始化 21 } 22 for(int i = 1 ;i <= n ; i ++ )//处理最小 23 { 24 if( i == 1 )//特殊处理 25 { 26 ans[i] = a[i]; 27 if( a[i] != n ) 28 f[a[i]] = f[a[i]] +1; 29 } 30 else 31 { 32 if( a[i] == a[i-1] )//如果和前一个数相等 33 { 34 int k = find(1);//找到可以使用的最小的数（从1开始找） 35 ans[i] = k; 36 f[1]=find(f[k]+1);//把f[1]更新 37 } 38 else//不相等 39 { 40 int k = find(a[i]); 41 ans[i] = a[i];//直接赋值 42 f[k]=find(f[k]+1);//更新当前数 43 } 44 } 45 } 46 for(int i = 1 ;i <= n ; i ++ ) 47 { 48 cout << ans[i] << " "; 49 } 50 cout << endl; 51 for(int i = 1 ;i <= n ; i ++ )//初始化 52 { 53 f[i] = i; 54 } 55 for(int i = 1 ;i <= n ; i ++ )//处理最大 56 { 57 if( i == 1 )//特殊处理 58 { 59 ans[i] = a[i]; 60 if( a[i] != 1 ) 61 f[a[i]] = f[a[i]] -1; 62 } 63 else 64 { 65 int k = find(a[i]);//从当前数开始找可以使用的最大的数 66 if( a[i] == a[i-1] ) 67 { 68 ans[i] = k; 69 } 70 else 71 { 72 ans[i] = a[i]; 73 } 74 f[k]=find(f[k]-1);//更新 75 } 76 } 77 for(int i = 1 ;i <= n ; i ++ ) 78 { 79 cout << ans[i] << " "; 80 } 81 cout << endl; 82 83 } 84 return 0; 85 }
Codeforces Round #710 (Div.3) A-E题解
原文：https://www.cnblogs.com/wockcow/p/14608484.html