一些有趣简单的算法题，来看看吧

想要补发题解来着，，可是前些天加起来刷的题太多了，从今天开始写题解吧，大概有5个题还算是有点意思。
难度：codeforce div2的C以上
Talk is cheap show me your code（别只叭叭不动手）
CF14C
上古题，1700？笑了
题意：用两点表示一条线段的话，给你4条线段，问你能不能构成一个边是平行于对应坐标轴的矩形。
思路：1.四个点 2.四条边；抓住这两个条件去判断就行了

#include 
using namespace std;
#define ll long long

int main()
{
    map,ll> mp;
    ll x1,y1,x2,y2;
    ll cnt1=0,cnt2=0;
    for(ll i=0;i<4;i++)
    {
        cin>>x1>>y1>>x2>>y2;
        if(x1!=x2&&y1==y2) cnt1++;
        if(x1==x2&&y1!=y2) cnt2++;
        mp[{x1,y1}]++;
        mp[{x2,y2}]++;
    }
    bool flag = false;
    if(cnt1==2&&cnt2==2)
        flag = true;
    for(auto i=mp.begin();i!=mp.end();i++)
    {
    	if(i->second!=2)
    	{
    		flag=false;
    		break;
		}
	}
    if(flag)
        cout<<"YES"< 
Array and Operations CF1618D
 题意：给定n个数，你 *** 作k次，每次拿走两个数x和y，让目前的score+=x/y，注意x/y是向下取整的。最后的score是你 *** 作k次的得分和剩下所有元素的和。求score的最小值。
 一个div3的D，评到了1300分？？感觉很简单，无算法。
 思路：把k个最大的作为分母，然后再取k个最大的作为分子
 
#include 
#include 
#include 
using namespace std;
#define fastio ios::sync_with_stdio(false);cout.tie(false):cin.tie(false);
#define debug freopen("in.txt","r",stdin);
#define vi vector
#define vl vector
#define ll long long
int t,score,n,k;
int main()
{
    for(cin>>t;t;t--)
    {
        int a[110];
        cin>>n>>k;
        score=0;
        for(int i=1;i<=n;i++)
            cin>>a[i];
            sort(a+1,a+n+1);
        for(int i=0;i 
CF1608B
 题意：给n，a，b三个数，构造波形数组（比如1324就是一个波峰一个波谷的数组），数组长度为n（元素就用1-n就行），要求有a个波峰，b个波谷。能构造就输出构造了个啥，不能构造就不用输出了。
 div2 C以下B以上的难度，，不上不下的，也没有算法，思维题。
 思路：
 1.之前做过一个很像，要求是直接构造一个长度为n的波形数组，这个不过就是具体要求了几个波峰几个波谷。
 2.我们观察之后不难发现，3个数构成一个波峰或者波谷，然后每加两个数又能构成一个波峰或者波谷。那么显然a+b>n-2的时候无解，并且峰谷交替出现，abs（a-b）>1也是无解的
 3.同样的，不难发现我们要构造波峰波谷只要交换元素就行了，比如123交换为132或者312。
 4.对于3的进一步解释，不建议看，建议自己思考 。如果a=b那么我们交换的就是形如i2和i2+1个位置的元素，如果对于波峰数<波谷数，那么交换2i-1位置和2i位置的元素，如果波峰数>波谷数，交换
 n-i2+1和n-i2+2位置的元素
 
#include 
#include 
#include 
using namespace std;
#define fastio ios::sync_with_stdio(false);cout.tie(false):cin.tie(false);
#define debug freopen("in.txt","r",stdin);
#define vi vector
#define vl vector
#define ll long long
int p[100001];
int main()
{
	int t,a,b,n;
	for(cin>>t;t;t--)
    {
		cin>>n>>a>>b;
		for(int i=1;i<=n;i++)
            p[i]=i;
		if(abs(a-b)>1 || a+b>n-2)
        {
			cout<<-1< 
CF1598D Training Session
 教育场D题，需要组合数学，有一定难度
 题意：给定n个问题，题目有种类和难度两个信息，现在从中抽取3个组成一套题，要求，不能出现同一种类或者难度两次，问有多少种组成方法。
 思路：
 1.很浓的组合数学味道，也有三元组的味道，但是可以看出来这题就是组合数学做的。
 2.如果无限制条件，一共有Cn3个组合，现在有了限制条件我们叫减去一些组合，很自然的想到了容斥原理。
 3.关于容斥的过程，是这个题能上1700的关键，我们首先把所有的难度相同samea的和种类相同sameb的题数都记录下来作为预处理。我们发现，题目保证没有两个完全一样的problem，所以我们违规的三元组就是这样的：[（x1，y1），（x2，y2），（x1，y2）or（x2，y1）]
 也就是说我们我们发现有个题和另外两个中的一个共享了难度，和另一个共享了种类，我们姑且称这个问题为中心问题。用中心问题能组成（samea-1）*（sameb-1）违规三元组
 
对于最后这一部分，我们还可以把他视为二维图形上的坐标，三个点构成了一个不和规定的L型,对于每一个点我们去看看他能构成多少个L型，
 show the code
 
#include 
using namespace std;
long long t,n,a[200020],b[200020],samea[200020],sameb[200020];
signed main(){
    for(cin>>t;t;t--){
        cin>>n;
        for(int i=0;i<=n;i++)
           samea[i]=sameb[i]=0;
        long long ans=n*(n-1)*(n-2)/6;
        for(int i=0;i>a[i]>>b[i];
            samea[a[i]]++;sameb[b[i]]++;
        }
        for(int i=0;iCF1598C Delete Two Elements
 教育场C
 题意：给定一堆数，我从里面删去俩，要求删完之后平均值不能变，问你有多少种删去的方案
 注：1，2和2，1算是一种方案
 
很简单，我们知道删去这的这两数的平均值等于原本数组的平均值就行了。可不要暴力去做啊！
 emmmm，还是推导一下吧
 sum/n=（sum-now-x)/(n-2)
 x=(sum2)/n-now
 我们对于这个式子知道了如果sum2/n不是整数则无解
 
#include 
using namespace std;
#define ll long long
ll t,n,a[200000+20],ans,sum;
mapmp;
signed main()
{
    for(cin>>t;t;t--)
    {
        mp.clear();ans=0;sum=0;
        cin>>n;
        for(int i=0;i>a[i],sum+=a[i];
        sum*=2;
        if(sum%n)
        {
            cout<<"0"<注意
 ans+=mp[sum-a[i]];
 mp[a[i]]++;
 因为避免如同2，1和1，2这样的重复解，我们一开始没有对mp进行计数，但是我们对于一组now和x只要把其中的一个数+1，那么后来遍历的时候就会加上的。
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714000.html