1001：

Is Derek lying?

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3598 Accepted Submission(s): 999

Problem Description

Input

The first line consists of an integer

Output

For each test case,the output will be only a line.

Please print “

Sample Input

   
    2
3 1 3
AAA
ABC
5 5 0
ABCBC
ACBCB

Sample Output

   
    Not lying
Lying

只需要一个判断条件，若特判了整个问题就麻烦大了...wa到绝望的时候重写了一遍把特判都去了就过了...

首先，我们统计出Derek和Alfia答案相同的题目数量k1和答案不同的题目数量k2. 对于两人答案相同的题目，共有以下两种情况：

a.两人都对

b.两人都错

对于两人答案不同的题目，共有以下三种情况：

c.Derek对Alfia错

d.Alfia对Derek错

e.两人都错

于是我们可以列出一些方程： k1+k2=n a+b=k1 c+d+e=k2 a+c=x a+d=y 又a,b,c,d,e均为非负整数，且满足a,b<=k1;c,d,e<=k2 将a,b,d,e全部用c替换后需要同时满足以下四个条件： 0<=c<=k2 x-y<=c<=k2+x-y (x-y)/2<=c<=(k2+x-y)/2 x-k1<=c<=x 我们只需要判断这四段区间存不存在公共的整数点，如果存在，则说明Derek没有说谎；如果不存在，则说明Derek在说谎。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define MAXN 80000+5
using namespace std;

char s1[MAXN],s2[MAXN];

int main()
{
	int t;
	while(~scanf("%d",&t))
	{
		while(t--){
			memset(s1,0,sizeof(s1));
			memset(s2,0,sizeof(s2));
			int n,a1,a2;
			scanf("%d%d%d",&n,&a1,&a2); 
			cin>>s1;
			cin>>s2;
			int tong=0,yi=0;
			for(int i=0;i<n;i++){
				if(s1[i]==s2[i])tong++;
				 else yi++;
			}
//			if(a1<a2){
//			}
//			else{
//				int temp;
//				temp=a1;
//				a1=a2;
//				a2=temp;
//			}
//			if(max(a1,a2)==n){
//				if(min(a1,a2)<tong){
//					printf("Lying\n");
//				}
//				else{
//					if((a1+a2-tong)<=n&&(a1+a2)<=(tong*2+yi)&&(a1+a2)>=0&&(max(a1,a2)-min(a1,a2)<=yi)){
//						if(yi%2==0){
//							if((a1+a2)%2==1){
//								printf("Lying\n");
//							}
//							else{
//								printf("Not lying\n");
//							}
//						}
//						else{
//							if((a1+a2)%2==0){
//								printf("Lying\n");
//							}
//							else{
//								printf("Not lying\n");
//							}
//						}
//					}
//					else {
//						printf("Lying\n");
//					}			
//				}
//			}
//			else if(min(a1,a2)==0){
//				if(max(a1,a2)>yi){
//						printf("Lying\n");
//					}
//					else{
//						if((a1+a2-tong)<=n&&(a1+a2)<=(tong*2+yi)&&(a1+a2)>=0&&(max(a1,a2)-min(a1,a2)<=yi)){
//							if(yi%2==0){
//								if((a1+a2)%2==1){
//									printf("Lying\n");
//								}
//								else{
//									printf("Not lying\n");
//								}
//							}
//							else{
//								if((a1+a2)%2==0){
//									printf("Lying\n");
//								}
//								else{
//									printf("Not lying\n");
//								}
//							}
//						}
//						else {
//							printf("Lying\n");
//						}			
//					}
//			}
//			else{
//				if((a1+a2-tong)<=n&&(a1+a2)<=(tong*2+yi)&&(a1+a2)>=0&&(max(a1,a2)-min(a1,a2)<=yi)){
//					if(yi%2==0){
//						if((a1+a2)%2==1){
//							printf("Lying\n");
//						}
//						else{
//							printf("Not lying\n");
//						}
//					}
//					else{
//						if((a1+a2)%2==0){
//							printf("Lying\n");
//						}
//						else{
//							printf("Not lying\n");
//						}
//					}
//				}
//				else {
//					printf("Lying\n");
//				}			
//			}
			if((a1+a2-tong)<=n&&(max(a1,a2)-min(a1,a2)<=yi)){
					printf("Not lying\n");
			}
			else{
					printf("Lying\n");
			}
		}
	}
	return 0;	
}

1003：

Maximum Sequence

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1887 Accepted Submission(s): 671

Problem Description

Steph is extremely obsessed with “sequence problems” that are usually seen on magazines: Given the sequence 11, 23, 30, 35, what is the next number? Steph always finds them too easy for such a genius like himself until one day Klay comes up with a problem and ask him about it.

Given two integer sequences {ai} and {bi} with the same length n, you are to find the next n numbers of {ai}:

Input

The input contains no more than 20 test cases.
For each test case, the first line consists of one integer n. The next line consists of n integers representing {ai}. And the third line consists of n integers representing {bi}.
1≤n≤250000, n≤a_i≤1500000, 1≤b_i≤n.

Output

For each test case, print the answer on one line: max{

Sample Input

Sample Output

    
     27

     
      
       Hint
       For the first sample: 1. Choose 2 from {bi}, then a_2…a_4 are available for a_5, and you can let a_5=a_2-2=9; 2. Choose 1 from {bi}, then a_1…a_5 are available for a_6, and you can let a_6=a_2-2=9;

预处理：a_i -= i ，易证明从最小的b开始选每次选最大的一定可以使结果最大。证明思路：如果条件改为a_i<=max{a_j-j|b_k<=j<=n}，那么b的顺序与最后的结果无关。条件改回来后，由于每次要计算一个数的最大值时都有a_(n+1)...a_(i-1)在范围中，所以每次只需让a_i - i尽可能大，那么就把大的数尽早用上，每次一定考虑尽量多的数字，这样取得的数字就尽可能的大。所以说每次就是求区间最值，加在答案上。由于贪心的思路，每次要求的区间的下界是单调不降的，故可以用单调队列优化到O(n)的复杂度。由于1 ≤ b_i ≤ n，对b排序可以用哈希排序（桶排序）完成。进一步观察，可以发现这样贪心时 a_(n+1)...a_i 其实是单调不增的，所以并不需要每次求区间最值了，选第一个数时就选最大的，后面的选择顺序与最终结果无关了。

我一开始的做法也是每次取最大的，把比这个数小的都删除掉，然后把新生成的那个数也加进去，这样不断根据另一个数组（里面储存的是下标）进行取最大的，其中用到了multiset和multiset迭代器删除某一个而不是某一种元素。

//错误的做法 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<set>
#define mod 1000000007
using namespace std;

multiset<long long>s;   

long long a[250005*2],b[250005];
int main()
{
	long long n;
	while(~scanf("%d",&n))
	{
		s.clear();
		 memset(a,0,sizeof(a));
		 memset(b,0,sizeof(b));
		 for(long long i=1;i<=n;i++){
		 	scanf("%d",&a[i]);
		 	a[i]-=i;
			 s.insert(a[i]);
		 }
		 for(long long i=1;i<=n;i++){
		 	scanf("%d",&b[i]);
		 }		
		sort(b+1,b+n+1);
		long long res=0;
		long long cnt=1;
		int cnn=n; 
		 std::multiset<long long>::iterator it; 
		for(long long i=1;i<=n;i++){
			long long rr=0;
		 	rr=*s.rbegin();
			res= (res%mod+rr%mod)%mod;
//			cout<<rr<<" "<<rr-n-i<<endl;
		 	for(long long j=cnt;j<=b[i];j++){
			    multiset<long long>::iterator pos = s.find(a[j]);  
 		    	s.erase(pos);//remove one element with value 3  
// 		    	cout<<*s.rbegin()<<" ";
			}
			cnt=b[i]+1;
			s.insert(rr-n-i);  		
			cnn++;
			a[cnn]=	rr-n-i;
			cout<<*s.rbegin()<<endl;
		} 
//		for (std::set<long long>::iterator it=s.begin(); it!=s.end(); ++it)  
//   			 std::cout << ' ' << *it; 
//			 std::cout<< *s.rbegin(); 
		cout<<res<<endl;
	}
	return 0;	
} 



//正确做法 
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;

const int  num = 505000;
const long long mm=1000000007;
struct point{
    int val;
    int index;
};

bool cmp0(point a,point b){
    return a.val>b.val?true:false;
}
bool cmp1(int a,int b){
    return a<b?true:false;
}
point arr0[num];
int arr1[num];
int arr2[num];
int main(){
    int n,temp,vv,ans=0;;
    while(scanf("%d",&n)!=EOF){
        ans=0;vv=0;
        for(int i=0;i<n;i++){
            scanf("%d",&arr1[i]);
            point te;
            te.val=arr1[i]-i-1;
            te.index=i+1;
            arr0[i]=te;
        }
        for(int i=0;i<n;i++)
            scanf("%d",&arr2[i]);
        sort(arr0,arr0+n,cmp0);
        sort(arr2,arr2+n,cmp1);


        for(int i=0,j=0,p=0;i<n;){
            while(arr0[j].index<arr2[p])
                j++;
            if(arr2[p]<=arr0[j].index){
                arr1[i+n]=arr0[j].val;
                vv=arr0[j].val-i-1-n;
                i++;p++;
            }
             while(arr2[p]<=arr0[j].index){
                arr1[i+n]=arr0[j].val;
                i++;p++;
            }
            for(int i=n-1;i>=0;i--){
                if(arr0[i].val<vv){
                    arr0[i].val=vv;
                }else
                    break;
            }
        }
        for(int i=n;i<2*n;i++){
            //cout<<arr1[i]<<endl;
            ans=(ans+arr1[i])%mm;
            cout<<arr1[i]<<endl;
        }
        printf("%d\n",ans);
    }
    return 0;
}

1006：（矩阵快速幂待补）

Funny Function

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 713 Accepted Submission(s): 225

Problem Description

Function

Input

There is one integer T in the first line.
The next T lines,each line includes two integers N and M .
1<=T<=10000,1<=N,M<2^63.

Output

For each given N and M,print the answer in a single line.

Sample Input

Sample Output

   
    2
33

对于任意i>=1，当j>=3时，有

通过归纳法可以得到

进而推导出

通过矩阵快速幂求解

不会。。。不知道怎么就引进了矩阵。。。菜鸡。。。。

1011:

Regular polygon

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2924 Accepted Submission(s): 685

Problem Description

On a two-dimensional plane, give you n integer points. Your task is to figure out how many different regular polygon these points can make.

Input

The input file consists of several test cases. Each case the first line is a numbers N (N <= 500). The next N lines ,each line contain two number Xi and Yi(-100 <= xi,yi <= 100), means the points’ position.(the data assures no two points share the same position.)

Output

For each case, output a number means how many different regular polygon these points can make.

Sample Input

Sample Output

1
2

题意，二维平面上给N个整数点，问能构成多少个不同的正多边形。题解：容易得知只有正四边形可以使得所有的顶点为整数点。（具体证明可参考杨景钦在2017的国家队论文）所以正解即求出所有的正四边形个数。枚举2个点，然后暴力判断另外2个点的位置是否存在。复杂度 N*N*logN。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int N=505,M=105;
PII p[N];
int mp[M<<1][M<<1];

int main()
{
    int n;
    while (scanf("%d",&n)!=EOF) {
        memset(mp,0,sizeof(mp));
        for (int i=1;i<=n;i++) {
            scanf("%d%d",&p[i].first,&p[i].second);
            mp[p[i].first+M][p[i].second+M]++;
        }
        int ans=0;
        for (int i=1;i<=n;i++) {
            for (int j=i+1;j<=n;j++) {
                int x_1=p[i].first,y_1=p[i].second;
                int x_2=p[j].first,y_2=p[j].second;

                #define inbound(x) -100<=x&&x<=100
                //根据正方形的四个补角三角形全等 也就是说这四个三角形的变长和正方形的四个顶点有些关系 
                int x_3=x_2-y_1+y_2,y_3=y_2+x_1-x_2;
                int x_4=x_1-y_1+y_2,y_4=y_1+x_1-x_2;
                if (inbound(x_3)&&inbound(x_4)&&inbound(y_3)&&inbound(y_4)) {
                    ans+=mp[x_3+M][y_3+M]*mp[x_4+M][y_4+M];
                }

                x_3=x_2+y_1-y_2;y_3=y_2-x_1+x_2;
                x_4=x_1+y_1-y_2,y_4=y_1-x_1+x_2;
                if (inbound(x_3)&&inbound(x_4)&&inbound(y_3)&&inbound(y_4)) {
                    ans+=mp[x_3+M][y_3+M]*mp[x_4+M][y_4+M];
                }
                #undef inbound
            }
        }
        printf("%d\n",ans/4);
    }
    return 0;
}

官方题解

[多校补题]2017 Multi-University Training Contest 2 solutions BY 电子科技大学

1001：

Is Derek lying?

1003：

Maximum Sequence

1006：（矩阵快速幂 待补）

Funny Function

1011:

Regular polygon

1006：（矩阵快速幂待补）