“美登杯”上海市高校大学生程序设计邀请赛 (华东理工大学)
I.小花梨点外卖(签到成功)
题目链接:https://acm.ecnu.edu.cn/contest/173/problem/I/
题解:对两种优惠方案分别计算,取最小值
#include <bits/stdc++.h>
#define P pair<int,int>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int mod=998244353;
int main(){
int n,a,b,c,d;
cin>>n>>a>>b>>c>>d;
int sum=0;
int tmp;
for(int i=1;i<=n;i++){
scanf("%d",&tmp);
sum+=tmp;
}
int ts=sum;
if(sum>=a) sum-=b;
if(ts>=c) ts-=d;
cout<<min(sum,ts)<<endl;
return 0;
}
A.小花梨的字符串
题目链接:https://acm.ecnu.edu.cn/contest/173/problem/A/
题解:答案就是子串的子串个数.对(a[l]...a[r])的子串,输出((r-l+2)*(r-l+1)/2).
tip:这题刚开始没看懂,直接跳过写B题了,B题写完了发现怎么这么多人过,才发现是道签到题.
#include <bits/stdc++.h>
#define P pair<int,int>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
const int N=1e4+5;
const int mod=998244353;
char s[N];
int main(){
int n,q;
cin>>n>>q;
scanf("%s",s);
while(q--){
int l,r;
cin>>l>>r;
cout<<(1+r-l+1)*(r-l+1)/2<<endl;
}
return 0;
}
B.小花梨的三角形
题目链接:https://acm.ecnu.edu.cn/contest/173/problem/B/
题解:枚举每一个三角形.用multiset记录下三角形的三个顶点.用map记录出现的三角形类型.
怎么枚举三角形呢?我是先选择一个定点.,然后剩下的两个点延伸扩大.
tip:还有倒立的三角形,因为这个wa了一发.
#include <bits/stdc++.h>
#define P pair<int,int>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
const int N=200+5;
const int mod=998244353;
char s[N][N];
map<multiset<char>,int> m;
int main(){
int n;
cin>>n;
int t=n+1;
for(int i=1;i<=t;i++){
scanf("%s",s[i]+1);
}
int ans=0;
for(int i=1;i<=t;i++){
for(int j=1;j<=i;j++){
int x=i+1,y1=j,y2=j+1;//正立三角形
while(x<=t){
multiset<char> n1;
n1.insert(s[i][j]);
n1.insert(s[x][y1]);
n1.insert(s[x][y2]);
if(m[n1]==0) ans++,m[n1]=1;//计数
x++,y2++;
}
int y=j+1,x1=i,x2=i+1;//倒立三角形
while(y<=i&&x2<=t){
multiset<char> n1;
n1.insert(s[i][j]);
n1.insert(s[x1][y]);
n1.insert(s[x2][y]);
if(m[n1]==0) ans++,m[n1]=1;//计数
y++,x2++;
}
}
}
cout<<ans<<endl;
return 0;
}
D.小花梨的取石子游戏
题目链接:https://acm.ecnu.edu.cn/contest/173/problem/D/
题解:
- (n) 为 1,先手必胜.
- (n) 个数都为 1,n为奇数,先手必胜,否则后手必胜.
- 开始的连续的1的个数为奇数时,后手必胜,否则先手必胜.如:(1, 1, 1, 2),后手必胜.如:(1, 1, 1, 1,3),先手必胜.
#include <bits/stdc++.h>
#define P pair<int,int>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int mod=998244353;
int a[N];
int m[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
if(n==1){
puts("First");
return 0;
}
for(int i=n+1;i<=2*n;i++) a[i]=a[i%n];
int f=0;
for(int i=2*n-1;i>=1;i--){
if(a[i]==1) m[i]=m[i+1]+1,f=1;//计算连续的1
}
for(int i=1;i<=n;i++){
if(f==0){//没有1先手必胜
puts("First");
}
else{
if(m[i]>=n) m[i]=n;
if(m[i]==n){//如果全是1,1的个数是偶数,先手必胜 ,否则后手必胜
if(n%2==1) puts("First");
else puts("Second");
}
else{
if(m[i]%2==1){//开头的1的个数为奇数,后手必胜,否则先手必胜.
puts("Second");
}
else puts("First");
}
}
}
return 0;
}
C.小花梨判连通
题目链接:https://acm.ecnu.edu.cn/contest/173/problem/C/
题解:对每个图都进行染色,对于(i,j)来说,如果在每个图中他们是连通的,那么他们的颜色应该都是想同的,用vector se[i]来存储每个点在k个图中颜色值,map<vector
#include <bits/stdc++.h>
#define P pair<int,int>
#define fir first
#define sec second
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int mod=998244353;
int vis[N];
vector<int> v[N];
vector<int> se[N];
map<vector<int>,int> c;
void bfs(int now,int color){
queue<int> q;
q.push(now);
vis[now]=color;
while(!q.empty()){
now=q.front();q.pop();
int nxt;
for(int i=0;i<v[now].size();i++){
nxt=v[now][i];
if(vis[nxt]==0) q.push(nxt),vis[nxt]=color;
}
}
}
int main(){
int n,k;
scanf("%d%d",&n,&k);
while(k--){
int m;
scanf("%d",&m);
int a,b;
memset(v,0,sizeof(v));
for(int i=1;i<=m;i++){
scanf("%d%d",&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
int cnt=0;
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
if(vis[i]==0) bfs(i,++cnt);
se[i].push_back(vis[i]);
}
}
for(int i=1;i<=n;i++){
c[se[i]]++;
}
for(int i=1;i<=n;i++){
printf("%d
",c[se[i]]);
}
return 0;
}
其他不会了,补题去..............
----------------------------------5/19号更新--------------------------分割线-----------------------
E.小花梨的数组(线段树)
题目链接:https://acm.ecnu.edu.cn/contest/173/problem/E/
题解:题目涉及到区间修改,单点查询,线段树刚好有此特性.
对每个数进行质因子分解并保存在vector fac[(i)]中,
线段树维护两个数组mul(乘法标记)和d(除法标记).
一系列操作后,每个点的结果总是fac去掉前面的除法操作数(divnum)的质因子后的乘积,再乘以乘法操作数 (mulnum)个的第一个质因子.
#include <bits/stdc++.h>
#define P pair<int,int>
#define fir first
#define sec second
#define lc ((rt) << 1)
#define rc ((rt) << 1 | 1)
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int mod=1e9+7;
//小花梨的数组
int a[N];
int pri[1010],tot;
int vis[1010];
vector<int> fac[N];
int mul[N*4],d[N*4];
int mulnum,divnum;
void push_down(int rt){
if(mul[rt]||d[rt]){
if(mul[rc]>=d[rt]) mul[rc]-=d[rt];
else d[rc]+=(d[rt]-mul[rc]),mul[rc]=0;
if(mul[lc]>=d[rt]) mul[lc]-=d[rt];
else d[lc]+=(d[rt]-mul[lc]),mul[lc]=0;
mul[lc]+=mul[rt];
mul[rc]+=mul[rt];
mul[rt]=d[rt]=0;
}
}
void init(){
for(int i=2;i<=1000;i++){
if(!vis[i]) pri[++tot]=i;
int j=i;
while(j*i<=1000){
vis[i*j]=1;
j++;
}
}
}
ll qp(ll x,int n){
ll res=1;
while(n){
if(n&1){
res=res*x%mod;
}
n>>=1;
x=x*x%mod;
}
return res;
}
void Update(int L,int R,int rt,int l,int r,int tree[],int op){
if(L<=l&&R>=r){
if(op==1) tree[rt]++;
else{
if(mul[rt]) mul[rt]--;
else tree[rt]++;
}
return;
}
push_down(rt);
int m=(l+r)>>1;
if(L<=m) Update(L,R,rt<<1,l,m,tree,op);
if(R>m) Update(L,R,rt<<1|1,m+1,r,tree,op);
}
void query(int x,int rt,int l,int r){
if(l==r){
divnum=d[rt];
mulnum=mul[rt];
return;
}
push_down(rt);
int m=(l+r)>>1;
if(x<=m) query(x,rt<<1,l,m);
else query(x,rt<<1|1,m+1,r);
}
int main(){
init();
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
int x=a[i];
for(int j=1;j<=tot&&pri[j]*pri[j]<=a[i];j++){
while(x%pri[j]==0) x/=pri[j],fac[i].push_back(pri[j]);
}
if(x!=1) fac[i].push_back(x);
}
while(m--){
int op,l,r;
scanf("%d",&op);
if(op==1){
scanf("%d%d",&l,&r);
Update(l,r,1,1,n,mul,op);
}
else if(op==2){
scanf("%d%d",&l,&r);
Update(l,r,1,1,n,d,op);
}else if(op==3){
int p;
scanf("%d",&p);
query(p,1,1,n);
if(divnum>=fac[p].size()) puts("1");
else{
int ans=1,tmp=fac[p][divnum];
for(int i=divnum;i<fac[p].size();i++){
ans*=fac[p][i];
}
ans=(ll)ans*qp(tmp,mulnum)%mod;
printf("%d
",ans);
}
}
}
return 0;
}