上海大学oj比赛

自用笔记算法

上海大学oj比赛

A

题目要求

输出矩阵中每一列1的个数

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
#define maxn 105
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
int a[maxn][maxn];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,m;
	while(cin>>n>>m){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++) cin>>a[i][j];
		}
		for(int i=1;i<=m;i++){
			int ans=0;
			for(int j=1;j<=n;j++){
				if(a[j][i]==1) ans++;
			}
			if(i==1) cout<<ans;
			else cout<<" "<<ans;
		}
		cout<<endl;
	}
	return 0;
}

B

题目要求

描述
假设神无月的段位系统如下：
从低到高的段位依次简记为：D、C、B、A、S。玩家打排位赛，每胜利1局增加10分，输1局扣除5分。每一个段位都需要积分，累计100分才可以进入晋级赛，
晋级赛采用三局两胜制（3局中达到2局胜利就晋级成功，有2局失败就算晋级失败, 连胜或连败两局，第三局不需要打了）。晋级成功后，成为下一个段位，
积分变为0，重新开始算分；如果晋级失败，则积分变为60，重新开始算分。为方便计算，如果该玩家一直输，积分降为0后，不再降分，也不会掉段位。
大圣同学最近对神无月非常喜欢，一直在努力成为王者。他从新兵0分开始打排位赛(刚开始处在段位D)，他告诉你最近若干场比赛的最后胜利情况，请你写
个算法猜猜他现在所处的段位。当段位到达S时，段位将不再提高。

输入
有若干组数据。
每组的第一行为一个N（0<N<500），表示有N场比赛数据。
第二行有N个数字，每个数字之间有空格隔开，每个数字代表每场比赛的输赢情况，1表示赢，0表示输。
注意：当第n场比赛结束时，若大圣同学正处于晋级赛，并且还无法决定晋级成功或失败，那么可以忽略这场晋级赛

输出
对于每组比赛数据，输出最后所处的段位的一个英文字符（D、C、B、A、S这五个段位中的一个）

样例输入
15
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
30
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1

样例输出
C
B

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
#define maxn 550
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
int a[maxn];
int point,flag;
char cur;
int win[3],len;
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n;
	while(cin>>n){
		for(int i=1;i<=n;i++) cin>>a[i];
		flag=0,point=0,cur='D';
		mm(win,0),len=0;
		for(int i=1;i<=n;i++){
			if(cur=='S') break;
			if(flag==0){
				if(a[i]==1) point+=10;
				if(a[i]==0){
					point-=5;
					if(point<0) point=0;
				}
				if(point>=100) flag=1;
				continue;
			}
			if(flag==1){
				if(a[i]==1) win[len++]=1;
				if(a[i]==0) win[len++]=0;
				if(len==2 && win[0]==1 && win[1]==1){
					if(cur=='A') cur='S';
					else cur=char(cur-1);
					point=0,mm(win,0),len=0,flag=0;
					continue;
				}
				if(len==2 && win[0]==0 && win[1]==0){
					point=60,mm(win,0),len=0,flag=0;
					continue;
				}
			}
			if(len==3){
				int f=0;
				for(int i=0;i<3;i++) if(win[i]==1) f++;
				if(f>=2){
					if(cur=='A') cur='S';
					else cur=char(cur-1);
					point=0;
				}
				else point=60;
				mm(win,0),len=0,flag=0;
			}
		}
		cout<<(char)cur<<endl;
	}
	return 0;
}

思路

模拟
注意点：
分减到负数直接为0
分只要超过100进入晋级赛
连胜2场或连输2场 已经知道结果无需打第三场晋级赛
段位到S后直接输出结果 无需判断后续
DCBAS可以用数组存储 本方法中需要注意A的后面是S

C

题目要求

问字符串中最多可以组成多少个I LOVE CES（不区分大小写，没有空格，即只要有这8个字符就可以组成一个

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
int hashh[30];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	string s;
	while(cin>>s){
		int ans=inf;
		mm(hashh,0);
		for(int i=0;i<s.length();i++) if(s[i]>='A' && s[i]<='Z') s[i]=char(s[i]+32); 
		for(int i=0;i<s.length();i++) hashh[s[i]-'a'+1]++;
//		for(int i=1;i<=26;i++) cout<<hashh[i]<<" "; cout<<endl;
		ans=min(ans,hashh['i'-'a'+1]);
		ans=min(ans,hashh['l'-'a'+1]);
		ans=min(ans,hashh['o'-'a'+1]);
		ans=min(ans,hashh['v'-'a'+1]);
		ans=min(ans,hashh['e'-'a'+1]/2);
		ans=min(ans,hashh['c'-'a'+1]);
		ans=min(ans,hashh['s'-'a'+1]);
		cout<<ans<<endl;
	}
	return 0;
}

思路

统计字母的个数的最小值 注意e/2即可

D

题目要求

求n个数字取任意k个有多少种方法

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
#define maxn 105
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
int a[maxn][maxn];
int n;
LL quick_pow(LL x,LL y){
	LL re=1,base=x%mod;
	while(y){
		if(y&1) re=(re*base)%mod;
		base=(base*base)%mod;
		y>>=1;
	}
	return re;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	while(cin>>n){
		cout<<quick_pow(2,n)-1<<endl;
	}
	return 0;
}

思路

2^n-1
快速幂

E

题目要求

输入一个字符串 a代表0···z代表25 相当于26进制数 把它转换成m进制数 输出结果

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
int a[15];
int len;
LL base[15]; 
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	base[0]=(LL)1;
	for(int i=1;i<=10;i++) base[i]=base[i-1]*(LL)26;
	string s;
	int m;
	while(cin>>s>>m){
		mm(a,0),len=0;
		stack<int>ss;
		for(int i=0;i<s.length();i++) a[++len]=(int)(s[i]-'a');
		LL ans=0;
 		for(int i=len;i>=1;i--) ans+=base[len-i]*a[i];
		if(ans==0){
			cout<<"0"<<endl;
			continue;
		}
		while(ans){
			ss.push(ans%(LL)m);
			ans/=(LL)m;
		}
		while(!ss.empty()){
			cout<<ss.top();
			ss.pop();
		}
		cout<<endl;
	}
	return 0;
}

思路

用栈模拟
注意ans=0的情况 特判

F

题目要求

描述
如果一个序列有奇数个正整数组成，不妨令此序列为a1,a2,a3,…,a2∗k+1(0<=k)，并且a1,a2…ak+1是一个严格递增的序列，ak+1,ak+2,…,a2∗k+1,是一个严格递减的序列，则称此序列是A序列。
比如1 2 5 4 3就是一个A序列。
现在Jazz有一个长度为n的数组，他希望让你求出这个数组所有满足A序列定义的子序列里面最大的那个长度。（子序列可以不连续）
比如1 2 5 4 3 6 7 8 9，最长的A序列子串是1 2 5 4 3。

输入
多组输入，每组两行。
第一行是n，表示给的数组的长度。
第二行有n个数(int范围)，即给你的数组。
1<=n<=500000。

输出
每组输入输出一行，即最长的A序列子串的长度。

样例输入
9
1 2 5 4 3 6 7 8 9

样例输出
5

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
#define maxn 500050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
int a[maxn],l[maxn],r[maxn]; 
int s[maxn],len;
int main(){
//  freopen("input.txt","r",stdin);
//  freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n;
    while(cin>>n){
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) l[i]=r[i]=1;
        mm(s,0);
        s[1]=a[1],len=1;
        for(int i=2;i<=n;i++){
            if(a[i]>s[len]){
                s[++len]=a[i];
                l[i]=len;
            }
            else{
                int k=lower_bound(s+1,s+1+len,a[i])-s;
                s[k]=a[i];
                l[i]=k;
            }
        }
        mm(s,0);
        s[1]=a[n],len=1;
        for(int i=n-1;i>=1;i--){
            if(a[i]>s[len]){
                s[++len]=a[i];
                r[i]=len;
            }
            else{
                int k=lower_bound(s+1,s+1+len,a[i])-s;
                s[k]=a[i];
                r[i]=k;
            }
        }
//      for(int i=1;i<=n;i++) cout<<l[i]<<" "; cout<<endl;
//      for(int i=1;i<=n;i++) cout<<r[i]<<" "; cout<<endl;
        int ans=0;
        for(int i=1;i<=n;i++) ans=max(ans,min(2*l[i]-1,2*r[i]-1));
        cout<<ans<<endl;
    }
    return 0;
}

思路

预处理每个位置 以该数为终点1到pos方向的lis用数组l存储 以该数为终点n到pos方向的lis用数组r存储
数组r从末尾遍历等价于正序的lis 所以算法不变
lis用nlogn的算法 防止超时 把l和r更新加入其中即可
ans更新max(ans,2×min(l[i],r[i])-1)即可

G

题目要求

敌方和我方有一些怪兽 每一个怪兽有一个生命值和攻击力 对方怪兽的出场顺序已知 每只怪兽每秒进行一次攻击 直到一方死亡为止
问我方改变怪兽出场顺序后可不可以战胜对方(对方无怪兽 我方至少有一只)

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
vector<pii>s1,s2;
int cmp(pii x,pii y){
	if(x.se==y.se) return x.fi<y.fi;
	return x.se>y.se;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=0;i<=n;i++) s1.clear(),s2.clear();
		for(int i=1;i<=n;i++){
			int x,y;
			cin>>x>>y;
			s1.pb(mp(x,y));
		}
		for(int i=1;i<=n;i++){
			int x,y;
			cin>>x>>y;
			s2.pb(mp(x,y));
		}
		sort(s2.begin(),s2.end(),cmp);
		int len1=0,len2=0;
		for(;len1<n && len2<n;){
			int temp1=ceil((double)s1[len1].fi/(double)s2[len2].se);
			int temp2=ceil((double)s2[len2].fi/(double)s1[len1].se);
			if(temp1<temp2){
				s2[len2].fi-=s1[len1].se*temp1;
				len1++;
			}
			else if(temp1>temp2){
				s1[len1].fi-=s2[len2].se*temp2;
				len2++;
			}
			else len1++,len2++;
		}
		if(len2<n) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

思路

贪心
我方希望用攻击力最大 生命值最小的怪兽先跟对方打 所以先排序 模拟战斗过程即可
temp1表示敌方死亡时间 temp2表示我方死亡时间 注意上取整 模拟三种情况即可

H

题目要求

描述
给定一个长度为n的非负整数序列，下标为0,1,…,n−1.
定义：sequence(K)： 由下标为K的倍数组成的子序列,即下标为0,K,2K,…,[n−1/k]∗k
query(K,S): 询问sequence(K)中的第S大的数字

输入
第一行一个整数T，表示测试组数。
对于每组数据，第一行输入两个整数n,m，1<=n<=20000, 1<=m<=100000，n表示序列的长度，m表示询问个数。
接下来一行是n个整数a0,a1,..,an−1,0<=ai<231, i=0,1,…,n−1，表示序列。
接下来m行，每行两个整数K,S
0<K<=109, 1<=S<=n

输出
每组数据对于每个询问输出一行，若sequence(K)的元素个数小于S，输出−1；否则输出query(K,S)

样例输入
1
5 2
2 5 3 4 1
2 4
2 1

样例输出
-1
3

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#define maxn 20050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
vector<LL>e[maxn];
LL a[maxn];
int cmp(LL x,LL y){
	return x>y;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		for(int i=0;i<=n;i++) e[i].clear();
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j+=i){
				e[i].pb(a[j]);
			}
			sort(e[i].begin(),e[i].end(),cmp);
		}		
		for(int i=1;i<=m;i++){
			int k,s;
			cin>>k>>s;
			if(k>=n){
				if(s>1) cout<<"-1"<<endl;
				else cout<<a[1]<<endl;
			}
			else{
				if(e[k].size()<s) cout<<"-1"<<endl;
				else cout<<e[k][s-1]<<endl;
			}
		}
	} 
	return 0;
}

思路

用vector存储
一维坐标表示间隔大小 每一行放的是该间隔大小下的所有数字 排序
输出时需要判断k>=n的情况(因为预处理是默认k<=n 未考虑k>n的情况)
若s==1 输出数组的第一个数字

I

题目要求

描述
有一天，空和白很无聊，决定玩盛大游戏，考虑到两个人玩，他们随便掏了一个游戏出来：在一个n∗m的棋盘上，首先把史蒂芬妮·多拉放在左上角(1,1)的位置
每次一个人可以将她往下，往右，往右下丢一格。当前回合，谁不能丢史蒂芬妮，谁就输了。（注意，不可以把活人丢出棋盘啦！）游戏总是空先手
白说，这是一个垃圾游戏！我们每次把史蒂芬妮丢素数个位置吧！（换句话说，每次丢2或3或5或7或…格）空答应了。
我们都知道，空和白都很聪明，不管哪方存在一个可以必胜的最优策略，都会按照最优策略保证胜利。
玩了一局，空已经知道了这个游戏的套路，现在他决定考考你，对于给定的n和m，空是赢是输？如果空必胜，输出“Sora”（无引号）；
反之，输出“Shiro”（无引号）

输入
第一行有一个T表示数组组数，1<=T<100000
从第二行开始，每行为棋盘大小，n、m分别表示行列。
1=<n<=500，1=<m<=500

输出
对于每组数据，按题目要求输出。

样例输入
4
1 1
2 2
10 10
30 30

样例输出
Shiro
Shiro
Shiro
Sora

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<bits/stdc++.h>
#define maxn 500
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
int vis[maxn+5],prime[maxn+5],len=0;
int dp[maxn][maxn];
void pur_solve(){
	mm(vis,0),vis[0]=vis[1]=1;
	int m=sqrt(maxn+0.5);
	for(int i=2;i<=m;i++){
		if(!vis[i]){
			for(int j=i*i;j<=maxn;j+=i) vis[j]=1;
		}
	}
	for(int i=0;i<=maxn;i++){
		if(!vis[i]) prime[len++]=i;
	}
}
int dfs(int x,int y){
	if(dp[x][y]!=-1) return dp[x][y];
	for(int i=0;i<len && x>=prime[i];i++){
		if(dfs(x-prime[i],y)==0){
			dp[x][y]=1;
			return dp[x][y];
		}
	}
	for(int i=0;i<len && y>=prime[i];i++){
		if(dfs(x,y-prime[i])==0){
			dp[x][y]=1;
			return dp[x][y];
		}
	}
	for(int i=0;i<len && x>=prime[i] && y>=prime[i];i++){
		if(dfs(x-prime[i],y-prime[i])==0){
			dp[x][y]=1;
			return dp[x][y];
		}
	}
	dp[x][y]=0;
	return dp[x][y];
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	pur_solve();
	int t;
	scanf("%d",&t);
	mm(dp,-1);
	while(t--){
		int n,m;
		scanf("%d%d",&n,&m);
		dp[0][0]=dp[0][1]=dp[1][0]=dp[1][1]=0;
		if(dfs(n-1,m-1)) puts("Sora");
		else puts("Shiro");
	}
	return 0;
}

思路

博弈+记忆化搜索
如果一个点能够走到必败点 那它就是必胜点
如果一个点走不到必败点 只能走到必胜点 这个点就是必败点
可以将问题转化成取石子：
有两堆石子，数量分别为n个和m个（n*m的棋盘），每次可以取走其中一堆质数个石子，
也可以同时取走两堆数量相同的质数个石子，到谁不能取谁失败
很明显，(0, 0)，(0,1)，(1,0)都是必输态
那么(2,0)，(0,2)，(2,1)，(0,3)，(3,0)，(0,3)，……，(k,1)，(1,k)，(k+1,0)，(0,k+1)（k为质数）都是必赢态，因为它们都可以一步取到必输态
因为n和m为500，直接记忆化搜索预处理
dp[x][y]==0表示(x,y)状态必输，dp[x][y]==1表示(x,y)状态必赢
那么如果(x,y)的前驱只要有一个是必输态，那么(x,y)就是必赢态，否则必输

J

题目要求

描述
欧拉函数ϕ(n)被定义1~n中与n互质的数的个数。例如ϕ(5)=4，因为1,2,3,4这四个数字与5互质。
定义f函数:
f(n)=∑i=233n−233ϕ(i)∗[n/i]
其中[n/i]表示n除以i所得到的商

输入
第一行一个整数T，表示测试组数。对于每组数据，输入一行，包含一个数字n，466<=n<=108

输出
每组数据输出一行，表示函数值f(n)对1000000007取模

样例输入
2
1068
972

样例输出
293824
222698

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
LL n;
LL euler_phi(LL n){
    LL m=(int)sqrt(n+0.5);
    LL ans=n;
    for(LL i=2;i<=m;i++) if(n%i==0){
    	ans=ans/i*(i-1);
    	while(n%i==0) n/=i;
	}
	if(n>1) ans=ans/n*(n-1);
	return ans;
    
}  
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		cin>>n;
		LL ans=(n+1)*n/2;
		for(int i=1;i<=232;i++) ans=(ans-euler_phi(i)*(n/i));
		for(int i=n;i>n-233;i--) ans=(ans-euler_phi(i)*(n/i));
		cout<<ans%mod<<endl;
	}
	return 0;
}

思路

打表求出公式f(n)=n*(n+1)/2
暴力删除1-233和n-233到n的值

K

题目要求

描述
最近盛大的一款游戏传奇世界极其火爆。游戏玩家John，想购买游戏中的装备。已知游戏的商店里有n件装备，第i件装备具有属性值ai，购买需要花费bi个金币。John想去购买这些装备，但是账号中只有m个金币，John是个很贪婪的家伙，他想购买尽可能多的装备。并且在保证购买到最多件装备的情况下，他还想让他所购买的装备当中拥有最小属性值的装备的属性值尽可能大。

输入
输入测试组数T，每组数据第一行输入整数n(1<=n<=100000)和m(1<=m<=109), 接下来有n行，第i行有两个数ai, bi(1<=ai,bi<=10000).

输出
对于每组数据，输出两个数字，第一个数字代表John最多可以购买的装备数，第二个数代表在John购买最多件装备的前提下，所购买的装备当中拥有最小属性值的装备的最大属性值(输入数据保证至少可以购买一件装备)

样例输入
1
2 4
3 2
2 3

样例输出
1 3

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
vector<pii>s;
int n,m;
int sum,len;
int cmp(pii x,pii y){
	if(x.se==y.se) return x.fi>y.fi;
	return x.se<y.se;
}
bool check(int x){
	int num=0;
	int all=m;
	for(int i=0;i<s.size();i++){
		if(s[i].fi<x) continue;
		if(all-s[i].se<0) break;
		all-=s[i].se;
		num++;  
	}
	return num>=len;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	scanf("%d",&t);
	while(t--){
		s.clear();
		scanf("%d%d",&n,&m);
		int max_p; 
		for(int i=1;i<=n;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			max_p=max(max_p,x);
			s.pb(mp(x,y));
		}
		sort(s.begin(),s.end(),cmp);
		sum=0,len=0;
		for(int i=0;i<s.size();i++){
			if(sum+s[i].se>m) break;
			sum+=s[i].se;
			len++;
		}
		int l=0,r=max_p,mid,ans;
		while(l<=r){
			mid=(l+r)>>1;
			if(check(mid)){
				l=mid+1;
				ans=mid;
			}
			else r=mid-1;
		}
		printf("%d %d\n",len,ans);
	}
	return 0;
}

思路

先把装备按照cost从小到大排序 求出最多能购买多少装备
再二分最小属性

M

题目要求

描述
小Y正在观测y地区的风力情况，他在一条直线上依此设定了n个观测点，并观测与直线垂直方向的风力值，风力有时是正向的也有时是反向的，规定正向时的风力值为正数，他发现每次风力值的变化都可以表示为观测点上一条线段[L,R]上的同时增强或者减弱。小Y希望能够实时统计这些观测点的数据，并且实时分析这些观测点在历史中到达的风力最大绝对值，但是他无法同时对大量的观测点进行分析, 更重要的是他记不住这些观测点过去的风力大小，于是他希望你来用计算机帮助他完成这个任务。
你简化了这个问题，将问题分为两种查询：
1.对观测点[L,R]上的风力正向增强X。（X为负数表示正向减弱，即反向加强）
2.查询观测点A上的历史风力最大绝对值。

输入
第一行有一个整数T表示数据组数。（T<=10）
接着有T组数据，每组数据第一行是整数n和q，表示观测点个数和查询次数。
第二行有n个数a1,…,an，表示每个观测点的风力初始值。
接着有q行，表示q次操作，格式为：
1 L R X：表示对[L，R]线段上的正向风力同时增强x。
2 A：表示查询A点的历史风力最大绝对值。
1<=n,q<=100000。
1<=L,R,A<=n
−10000<=ai, X<=10000

输出
对每次询问2，输出一个数字表示风力值并换行。

样例输入
1
5 6
1 -1 2 3 -3
1 1 5 1
2 1
2 2
1 2 4 -5
2 2
2 3

样例输出
2
1
5
3

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int n,q;
int maxx[maxn<<2],minn[maxn<<2];
int cur[maxn<<2];
void build(int l,int r,int rt){
	if(l==r){
		cin>>maxx[rt];
		cur[rt]=minn[rt]=maxx[rt];
		return;
	}
	cur[rt]=minn[rt]=maxx[rt]=0;
	int m=(l+r)>>1;
	build(lson);
	build(rson);
}
void push_down(int rt){
	if(cur[rt] || maxx[rt] || minn[rt]){
		maxx[rt<<1]=max(maxx[rt<<1],cur[rt<<1]+maxx[rt]);
		minn[rt<<1]=min(minn[rt<<1],cur[rt<<1]+minn[rt]);
		maxx[rt<<1|1]=max(maxx[rt<<1|1],cur[rt<<1|1]+maxx[rt]);
		minn[rt<<1|1]=min(minn[rt<<1|1],cur[rt<<1|1]+minn[rt]);
		cur[rt<<1]+=cur[rt];
		cur[rt<<1|1]+=cur[rt];
		minn[rt]=maxx[rt]=cur[rt]=0;
	} 
}
void update(int L,int R,int x,int l,int r,int rt){
	if(L<=l && r<=R){
		cur[rt]+=x;
		maxx[rt]=max(maxx[rt],cur[rt]);
		minn[rt]=min(minn[rt],cur[rt]);
		return;
	}
	int m=(l+r)>>1;
	push_down(rt);
	if(m>=L) update(L,R,x,lson);
	if(m<R) update(L,R,x,rson);
}
int query(int k,int l,int r,int rt){
	if(l==r) return max(abs(maxx[rt]),abs(minn[rt]));
	push_down(rt);
	int m=(l+r)>>1;
	if(m>=k) return query(k,lson);
	else return query(k,rson);
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		 cin>>n>>q;
		 build(1,n,1);
		 while(q--){
			int op;
			cin>>op;
		 	if(op==1){
		 		int l,r,x;
		 		cin>>l>>r>>x;
		 		update(l,r,x,1,n,1);
			}
			else{
				int y;
				cin>>y;
				cout<<query(y,1,n,1)<<endl;
			} 
		 }
	}
	return 0;
}

思路

线段树
区间修改 单点询问历史最大值/最小值绝对值的最大值
lazy数组换成cur maxn minn即可

M(扩展)

题目要求

区间修改 区间询问历史最小值
对于每次q一次update后query当前区间输出结果
题目链接

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int n;
LL minn;
struct node{
	LL m,sm,lm,cur,mcur;
}tree[maxn<<2];
void pushup(int rt){
	tree[rt].sm=tree[rt].m=min(tree[rt<<1].m,tree[rt<<1|1].m);
	tree[rt].lm=min(tree[rt].lm,tree[rt].m);
}
void pushdown(int rt){
	if(tree[rt].cur||tree[rt].mcur){  
        LL k=tree[rt].mcur;        
        tree[rt<<1].mcur=min(tree[rt<<1].mcur,tree[rt<<1].cur+k);
        tree[rt<<1].cur+=tree[rt].cur;  
        tree[rt<<1].lm=min(tree[rt<<1].mcur+tree[rt<<1].sm,tree[rt<<1].lm);  
        tree[rt<<1].m+=tree[rt].cur;  
        tree[rt<<1|1].mcur=min(tree[rt<<1|1].mcur,tree[rt<<1|1].cur+k);  
        tree[rt<<1|1].cur+=tree[rt].cur;  
        tree[rt<<1|1].lm=min(tree[rt<<1|1].mcur+tree[rt<<1|1].sm,tree[rt<<1|1].lm);  
        tree[rt<<1|1].m+=tree[rt].cur;  
        tree[rt].cur=0;  
        tree[rt].mcur=0;  
    }  
}
void build(int l,int r,int rt){
	if(l==r){  
        cin>>tree[rt].m;  
        tree[rt].sm=tree[rt].lm=tree[rt].m;  
        tree[rt].cur=0;  
        tree[rt].mcur=0;  
        return;  
    }  
    tree[rt].cur=0;  
    tree[rt].mcur=0;  
    tree[rt].lm=INF;  
    int m=(l+r)>>1;  
    build(lson);  
    build(rson);  
    pushup(rt); 	
}
void update(int L,int R,LL c,int l,int r,int rt){
	if(L<=l&&r<=R){  
        tree[rt].cur+=c;  
        tree[rt].mcur=min(tree[rt].mcur,tree[rt].cur);  
        tree[rt].m+=c;  
        tree[rt].lm=min(tree[rt].mcur+tree[rt].sm,tree[rt].lm);        
        return ;  
    }  
    pushdown(rt);  
    int m=(l+r)>>1;  
    if(L<=m)update(L,R,c,lson);  
    if(m<R)update(L,R,c,rson);  
    pushup(rt);  
}
void query(int L,int R,int l,int r,int rt){
	if(L<=l&&r<=R){   
        minn=min(minn,tree[rt].lm);  
        return ;  
    }  
    int m=(l+r)>>1;  
    pushdown(rt);  
    if(L<=m)  query(L,R,lson);  
    if(m<R) query(L,R,rson);  
    pushup(rt);  
    return ;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	while(cin>>n){
		build(1,n,1);
		int q;
		cin>>q;
		while(q--){
			int x,y;
			LL l;
			cin>>x>>y>>l;
			minn=INF;
			update(x,y,l,1,n,1);
			query(x,y,1,n,1);
			cout<<minn<<endl;
		}
	}	
	return 0;
}

思路

每个节点需要有一个当前最小值m、一个历史最小值 lm，一个延迟标记累加和和指的是延迟标记累加的得到的结果cur
一个用来保存当cur多次累加时出现的最小和 mcur，一个延迟标记累加前的m值用 变量sm储存

本文标题:上海大学oj比赛

文章作者:Hippopmonkey

发布时间:2017-07-11, 14:02:17

最后更新:2018-04-02, 19:33:04

原始链接:http://xuboming8.github.io/2017/07/11/上海大学oj比赛/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 上海大学oj比赛
    1. 1.1. A
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
    2. 1.2. B
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. C
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. D
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. E
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. F
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
    7. 1.7. G
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
      3. 1.7.3. 思路
    8. 1.8. H
      1. 1.8.1. 题目要求
      2. 1.8.2. 参考AC代码
      3. 1.8.3. 思路
    9. 1.9. I
      1. 1.9.1. 题目要求
      2. 1.9.2. 参考AC代码
      3. 1.9.3. 思路
    10. 1.10. J
      1. 1.10.1. 题目要求
      2. 1.10.2. 参考AC代码
      3. 1.10.3. 思路
    11. 1.11. K
      1. 1.11.1. 题目要求
      2. 1.11.2. 参考AC代码
      3. 1.11.3. 思路
    12. 1.12. M
      1. 1.12.1. 题目要求
      2. 1.12.2. 参考AC代码
      3. 1.12.3. 思路
    13. 1.13. M(扩展)
      1. 1.13.1. 题目要求
      2. 1.13.2. 参考AC代码
      3. 1.13.3. 思路
|