A. ACM赛制

直接模拟即可,需要注意总罚时可能会超出int范围,需要用long long保存。

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

const int MAXN = 1.5e6 + 5;
int n, k, tot = 0, cost = 0, st[MAXN];

void solve() {
	scanf("%lld%lld", &n, &k);
	tot = cost = 0;
	for(int i = 1; i <= n; i++) st[i] = 0;
	for(int i = 1; i <= k; i++) {
		int id, hh, mm; char msg[15];
		scanf("%lld:%lld-%lld:%s", &id, &hh, &mm, msg);		
		if(st[id] == 1) continue;
		if(msg[0] == 'a') {	// accepted
			++tot;
			cost += -20 * st[id] + hh * 60 + mm;
			st[id] = 1;
		} else {	// unaccepted
			--st[id];
		}
		
	}
	printf("%lld %lld", tot, cost);
}

signed main() {
	solve();
	return 0;
}

H. WF?刚打低程就想着WF?

定位是签到题。给出6个等级的比赛其中分Au、Ag、Cu,可以整体看成18个奖项,按照题意模拟即可。

#include <bits/stdc++.h>
using namespace std;
const int N=100;
int n,a[N];
map<string,int>mp;
string S[N];
int main(int argc, char *argv[]) {
	mp["LowerLevelProgrammingCompetition Cu"]=1,S[1]="LowerLevelProgrammingCompetition Cu";
	mp["LowerLevelProgrammingCompetition Ag"]=2,S[2]="LowerLevelProgrammingCompetition Ag";
	mp["LowerLevelProgrammingCompetition Au"]=3,S[3]="LowerLevelProgrammingCompetition Au";
	mp["SchoolCompetition Cu"]=4,S[4]="SchoolCompetition Cu";
	mp["SchoolCompetition Ag"]=5,S[5]="SchoolCompetition Ag";
	mp["SchoolCompetition Au"]=6,S[6]="SchoolCompetition Au";
	mp["ProvincialCompetition Cu"]=7,S[7]="ProvincialCompetition Cu";
	mp["ProvincialCompetition Ag"]=8,S[8]="ProvincialCompetition Ag";
	mp["ProvincialCompetition Au"]=9,S[9]="ProvincialCompetition Au";
	mp["Regional Cu"]=10,S[10]="Regional Cu";
	mp["Regional Ag"]=11,S[11]="Regional Ag";
	mp["Regional Au"]=12,S[12]="Regional Au";
	mp["ECfinal Cu"]=13,S[13]="ECfinal Cu";
	mp["ECfinal Ag"]=14,S[14]="ECfinal Ag";
	mp["ECfinal Au"]=15,S[15]="ECfinal Au";
	mp["WF Cu"]=16,S[16]="WF Cu";
	mp["WF Ag"]=17,S[17]="WF Ag";
	mp["WF Au"]=18,S[18]="WF Au";
	cin>>n;
	getchar();
	int ans=0;
	for(int i=1;i<=n;i++){
		string s;
		getline(cin,s);
		if(ans) continue;
		if(s.substr(s.length()-2)!="Fe") {
			int x=mp[s];
			a[x]++;
			while(a[x]>=3){
				a[x+1]++;
				a[x]-=3;
				x++;
			}
			if(x==18) ans=i;
		}
	}
	if(ans) cout<<ans<<endl;//有WF Au
	else {
		for(int i=18;i>=1;i--){
			if(a[i]){
				ans=i;
				break;
			}
		}
		if(ans) cout<<S[ans]<<endl;//有奖
		else cout<<"-1"<<endl;//Fe
	}
}

B. 邪恶?任何邪恶终将绳之以法!

考虑到数据范围,我们应该想办法限制每一次操作最多涉及到 logn\log{n} 个节点。

由于含有 nn 个节点的满二叉树,深度为 logn\log{n} 级别。我们操作点 xx 时,可以直接沿着 xx 的父亲方向往上走,直至根节点。

我们定义两个数组 cntcnt, distdist,其中这两个数组的含义如下:

cntxcnt_x 代表以 xx 为根节点的子树里有多少个小贼(包括节点 xx);

distxdist_x 代表以 xx 为根节点的子树中,所有小贼到节点 xx 的距离之和。

对于修改操作,我们可以在 O(logn)O(logn) 的范围内修改这两个数组;

对于查询操作,我们在往上走的过程中,维护这期间所经历的节点,并根据这两个数组计算结果。

具体来讲,我们设这一过程经历了节点 f,gf,g,其中 ggff 的父亲。treextree_x 代表以 xx 为根节点的子树,treextreeytree_x-tree_y 代表在 treextree_x 中删除 treeytree_y

那么,我们可以计算出 treegtreeftree_g-tree_f 的小贼数量 ucntucnt,和 treegtreeftree_g-tree_fucntucnt 个小贼到节点 gg 的距离 udistudist

考虑引入新的变量 cdistcdist,代表了节点 gg 到节点 xx 的距离(其中节点 xx 对应昊京现在的位置)。则 udist+ucntcdistudist+ucnt \cdot cdist 代表了节点 gg 对节点 xx 的贡献。

对于节点 xx,我们计算其所有祖先的贡献,再加上 distxdist_x,即是查询结果。

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

const int MAXN = 131071 + 5;
int dist[MAXN], cnt[MAXN], n, q;

int query(int x) {
	int res = dist[x], u = x >> 1, last = x, cdist = 1;
	while(u) {
		int ucnt = cnt[u] - cnt[last];
		int udist = dist[u] - dist[last] - cnt[last];
		res += udist + ucnt * cdist;
		
		++cdist;
		last = u;
		u >>= 1;
	}
	return res;
}

void modify(int x, int st) {
	int u = x, cdist = 0;
	while(u) {
		cnt[u] += st;
		dist[u] += st * cdist;
		
		++cdist;
		u >>= 1;
	}
}

void solve() {
	cin >> n >> q;
	for(int i = 1; i <= n; i++) cnt[i] = dist[i] = 0;
	while(q--) {
		int op, x; cin >> op >> x;
		if(op == 1) cout << query(x) << "\n"; 
		if(op == 2) modify(x, 1);
		if(op == 3) modify(x, -1);
	}	
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	solve();
	return 0;
}

E. 微积分?低程竟然有微积分?

处理前面若干项时,读到‘x‘或’^‘时便可得出一项系数,跟在后面的为指数。

建议最后一项单独处理,判断是否为常数项。

需要注意系数绝对值为1或指数为1时省略,存在常数项、首项为负的情况,小细节较多,比较考察选手的细心程度,考虑全面即可通过。

#include <bits/stdc++.h>
using namespace std;
string s;
int shou=1;//标记首项是否已读入
int fu=1;//存当前系数的符号
int xishu=0,zhishu=0;//存当前项的系数和指数
vector<int>xi,zhi;//存全部的指数和系数
inline int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int main(int argc, char *argv[]) {
	cin>>s;
	for(int i=0;i<s.length();i++){
		if(s[i]=='y'||s[i]=='\''||s[i]=='=') {}
		else if(s[i]>='0'&&s[i]<='9'){
			xishu=xishu*10+s[i]-'0';
		}
		else if(s[i]=='x'){
			if(xishu==0) xishu=1;
			if(fu==-1) xishu=-xishu;
			if(i<s.length()-1){
				if(s[i+1]=='^'){
					int j=i+2;
					while(j<s.length()&&s[j]>='0'&&s[j]<='9'){
						zhishu=zhishu*10+s[j]-'0';
						j++;
					}
					i=j-1;
				}
				else zhishu=1;
			}
			else zhishu=1;
			xi.push_back(xishu);
			zhi.push_back(zhishu);
			xishu=0,zhishu=0;
		}
		else if(s[i]=='+'||s[i]=='-'){
			if(shou){
				shou=0;
				if(s[i]=='-') fu=-1;
				continue;
			}
			if(s[i]=='+') fu=1;
			else fu=-1;
			xishu=0,zhishu=0;
		}
	}
	if(xishu>0){//存在常数项
		if(fu==-1) xishu=-xishu;
		zhishu=0;
		xi.push_back(xishu);
		zhi.push_back(zhishu);
	}
  cout<<"y=";//输出
	for(int i=0;i<xi.size();i++){
		if(xi[i]<0) {
			cout<<"-";
			xi[i]=-xi[i];
		}
		else if(i>0) cout<<"+";
		int fenzi=xi[i];
		int fenmu=zhi[i]+1;
		if(fenzi==fenmu){}
		else if(fenzi%fenmu==0){
			cout<<fenzi/fenmu;
		}
		else {
			int g=gcd(fenmu,fenzi);
			cout<<fenzi/g<<"/"<<fenmu/g;
		}
		cout<<"x";
		if(zhi[i]+1==1){}//指数为1时省略
		else cout<<"^"<<zhi[i]+1;
	}
	cout<<"+C"<<endl;//不定积分要+C!!!
	return 0;
}

SCI

Problem Statement

给你NN个串, 你选出KK个串拼接而成字典序最小的串

Solution

假设SiS_i表示第ii个串, 那么Si+Sj<Sj+SiS_i+S_j<S_j+S_i那么SiS_i一定会排在SjS_j前面, 很容易证明如果满足Sj+Sk<Sk+SjS_j+S_k<S_k+S_j那么有Si+Sk<Sk+SiS_i+S_k<S_k+S_i即满足传递性.

那么我们就能够先进行一次排序, 然后进行DP, 我们有两种DP方式.

  • 首先O(N4)O(N^4)的是我们强制fi,jf_{i,j}表示前ii个串选jj个并且以串ii结尾的字典序最小的串.
  • 或者为了消除后缀的影响, 我们可以倒过来DP, 我们设fi,jf_{i,j}表示倒数ii个串, 选出jj个串的最小后缀. 这种方法是O(N3)O(N^3)

旅行

Problem Statement

NN个点MM条边的无向图, 每条边用参数Ai,Bi,Ci,DiA_i,B_i,C_i,D_i表示, 时刻tt通过边ii的代价为Ci+DitC_i+\lfloor\frac{D_i}{t}\rfloor1N1-N的最小花费时间.

Solution

首先根据题意, 由于边权为Ci+DitC_i+\lfloor\frac{D_i}{t}\rfloor, 于是我们索性引入答案参数使得t=Ci+t+Ditt'=C_i+t+\lfloor\frac{D_i}{t}\rfloor, 由于CiC_i是常数, 出发时间 tt是单调递增函数, Dit\lfloor\frac{D_i}{t}\rfloor的一个关于出发时间的一个单调递减函数, 因此AiA_i到达BiB_i的边权等价于一个单峰函数其性质类似二次函数, 我们对其进行最小化跑一边Dijkstra即可, 至于有没有卡SPFA, 本人表示我没刻意卡.

B 蘑菇! 提莫来采蘑菇啦!

这题难度大概在CF2000左右,用来筛选dp比较好的选手

可以很简单的想到用一个dp1[i]dp1[i]来表示走到i这里的最短时间. 用一个dp2[i]dp_2[i]来表示走到i这里的方案数.

那么怎么计算从一个位置i使用机器人j能走到的地方呢? 可以发现用第k种机器人的本质是 最多有k种不同的数最长区间. 这是一个经典问题(参考最长连续不重复子序列),用双指针就可以处理. 每走到一个地方ii,就去扩展用第jj个机器人能走到的地方r[j]. 有3030种方案,双指针的时间复杂度为O(30n)O(30n) dpdp的时间复杂度为O(30n)O(30n).

不妨设 转移式:dp1[r[j]]=min(dp1[r[j]],dp1[i]+c[j])dp1[r[j]] = min(dp1[r[j]],dp1[i] + c[j]). 从i这里,使用第jj个机器人,能走到r[j]r[j]这个位置. 此时需要花费dp1[i]+c[j]dp1[i] + c[j]的时间,与dp1[r[j]]dp1[r[j]]去比较,取最小值. 注意初始化dp1[0]=0dp1[0] = 0.其余为正无穷,表示到达0这个位置需要最少花00的时间.

如果从i这个地方用第jj个机器人所花费的时间要比dp1[r[j]]dp1[r[j]]要小,那么 dp2[r[j]]dp2[r[j]]要用dp2[i]dp2[i]去更新.(dp2[r[j]]=dp2[i]dp2[r[j]] = dp2[i]) 如果dp1[r[j]]==dp1[i]dp1[r[j]] == dp1[i],说明之前就有方案到达过r[j]r[j],且与这次从i过来花费的时间相同. 于是从ii过来就是一种新方案.dp2[r[j]]+=dp2[i]dp2[r[j]] += dp2[i],就是加上到达ii已有的方案数. 注意取模.初始化dp2[0]=1dp2[0] = 1,其余为00.表示到达00这个位置初始就有11种方案.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10,mod = 998244353,INF = 1e17;
int n,m;
int a[N],c[N],dp1[N],dp2[N];
int r[35],cnt[35],mp[N][35];
void expand(int stpos,int j)
{
    if(mp[a[stpos]][j]) {
        mp[a[stpos]][j] -- ;
        if(mp[a[stpos]][j] == 0) cnt[j] -- ;
    }
    while(cnt[j] <= j && r[j] < n) {
        if(mp[a[r[j] + 1]][j] == 0)  {
            if(cnt[j] == j) break;
            cnt[j] ++ ;
        }
        mp[a[r[j] + 1]][j] ++ ;
        r[j] ++ ;
    }
}
signed main() {
    int T;
    cin >> T;
    while(T--) {
        cin >> n >> m;
        for(int i=1;i<=n;++i) cin >> a[i];
        for(int i=0;i<=m;++i) cin >> c[i];
        for(int i=0;i<=n;++i) {
            r[i] = dp2[i] = cnt[i] = 0;
            dp1[i] = INF;
            for(int j=0;j<=m;++j) mp[i][j] = 0;
        }
        dp1[0] = 0;dp2[0] = 1;
        for(int i=0;i<n;++i) //从i开始走 
            for(int j=0;j<=m;++j) {  //用第j个蘑菇 
                if(j == 0) r[j] = i + 1; //动手采集蘑菇,只能到下一个位置i+1.
                else expand(i,j);
                if(dp1[r[j]] == dp1[i] + c[j])  dp2[r[j]] = (dp2[r[j]] + dp2[i]) % mod;
                if(dp1[r[j]] > dp1[i] + c[j]) {
                    dp1[r[j]] = dp1[i] + c[j];
                    dp2[r[j]] = dp2[i];
                }
            }
        cout << dp1[n] << " " << dp2[n] << endl;
    }
    return 0;
}

D # 锁屏图案? 当然是第k长的最好看!

这题难度定位是稍微做过一些题的选手都要能做出来. 但是榜比较歪,很多人都不看这题.

直接暴力枚举所有的方案数,一共有9!=3628809! = 362880种方案,不多. 然后判断每种方案是否合法,合法的话计算下距离.

之后时排序,先按距离排,然后按字典序排,比较简单不多说了. 距离的话判相等只要精度误差在10710^{-7}以内就认为两种方案是相等的. 因为只有根号2,根号5,而且数量还不会很多.

时间复杂度O(999!)O(9 * 9 * 9!) //8 * 9是判断合法要的时间,另外1 * 9计算距离

#include<bits/stdc++.h> 
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N = 1e6 + 10;
double eps = 1e-7; //精度取10^-7 
struct node {
    int res[10];
    double dist;
    bool operator < (const node & cc) const{
        if( abs(dist - cc.dist) > eps) return dist > cc.dist;
        //先按距离排 
        for(int i=1;i<=9;++i) { //再按字典序排 
            if(res[i] != cc.res[i]) return res[i] > cc.res[i];
        }
    }
};
vector<node> v;
int a[10] = {0,1,2,3,4,5,6,7,8,9};
PII pos[10];
bool check(int l,int r,int mid) //判断l和r是否是连着,且mid在它们后面,这是非法的 
{
    int midpos,lpos,rpos;
    for(int i=1;i<=9;++i) {
        if(a[i] == mid) midpos = i;
        if(a[i] == l)   lpos = i;
        if(a[i] == r)   rpos = i;
    }
    if(lpos > rpos) swap(lpos,rpos);
    if(lpos + 1 == rpos && midpos > rpos) {
        return false;
    }
    return true;
}
double cal(int x,int y) //计算距离 
{
    double res = (pos[x].first - pos[y].first) * (pos[x].first - pos[y].first);
    res += (pos[x].second - pos[y].second) * (pos[x].second - pos[y].second);
    return sqrt(res);
}
void init()
{
    int n = 3;
    for(int i=1;i<=3;++i)
    {
        for(int j=1;j<=3;++j) {
            pos[3*(i-1) + j].first = i;  //初始化每行的x坐标
            pos[i + 3*(j-1)].second = i; //初始化每行的y坐标
        }
    }
    do { //这里用的是do{}while(next_permutation()),写dfs也可以 
        bool ok = true;
        ok &= check(1,3,2);ok &= check(1,7,4); //1-3 连着且2再他们后面,其它相同 
        ok &= check(3,9,6);ok &= check(7,9,8);
        ok &= check(3,7,5);ok &= check(1,9,5);
        ok &= check(2,8,5);ok &= check(4,6,5);
        if(ok == false) continue;
        node tmp;tmp.dist = 0;
        for(int i=1;i<=9;++i) {
            tmp.res[i] = a[i];
            if(i!=1) tmp.dist += cal(tmp.res[i],tmp.res[i-1]);
        }
        v.push_back(tmp);
    }while(next_permutation(a+1,a+1+9));
    sort(v.begin(),v.end());
}
signed main() {
    init();
    int T;cin >> T;
    while(T--) {
        int k;cin >> k;
        for(int i=1;i<=9;++i) cout << v[k-1].res[i] << " ";cout << endl;
    }
    return 0;
}
#include<bits/stdc++.h> //没精度误差 
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N = 1e6 + 10;
struct node {
    int id[10],dist[3];
};
int cmp2(int x1,int x2,int x3)
{
    if(x1 == 0 && x2 == 0 && x3 == 0) return 0;
    if(x1 >= 0 && x2 >= 0 && x3 >= 0) return 1;
    if(x1 <= 0 && x2 <= 0 && x3 <= 0) return -1;
    
    int flag = 0,res1 = 0,res2 = 0;
    int plan1 = 0,plan2 = 0;
    
    vector<PII> v;
    v.push_back({x1,5*x1*x1});
    v.push_back({x2,2*x2*x2});
    v.push_back({x3,1*x3*x3});
    sort(v.begin(),v.end());

    if(v[0].first <= 0 && v[1].first <= 0 && v[2].first >= 0) {
        res1 = v[2].second - v[0].second - v[1].second;
        res2 = 4 * v[0].second * v[1].second;
        if(res1 < 0) return -1;
        res1 = res1 * res1;
        if(res1 > res2) return 1;
        plan1 = -1;
    }
    return -cmp2(-x1,-x2,-x3);
    assert(0);
}
int cmp(node n1,node n2)
{
    int t[5];
    for(int i=0;i<3;++i) t[i] = n1.dist[i] - n2.dist[i];
    int res = cmp2(t[0],t[1],t[2]);
    if(res == 0) {
        for(int i=1;i<=9;++i) {
            if(n1.id[i] != n2.id[i]) return n1.id[i] > n2.id[i];
        }        
    }
    if(res == 1) return 1;
    return 0;
}
vector<node> v;
int a[10] = {0,1,2,3,4,5,6,7,8,9};
PII pos[10];
int check(int l,int r,int mid)
{
    int midpos,lpos,rpos;
    for(int i=1;i<=9;++i) {
        if(a[i] == mid) midpos = i;
        if(a[i] == l)   lpos = i;
        if(a[i] == r)   rpos = i;
    }
    if(lpos > rpos) swap(lpos,rpos);
    if(lpos + 1 == rpos && midpos > rpos) return false;
    return true;
}
PII cal(int x,int y)
{
    int delx = abs(pos[x].first - pos[y].first);
    int dely = abs(pos[x].second - pos[y].second);
    if(delx == 0 || dely == 0) return {2,delx + dely};
    if(max(delx,dely) / min(delx,dely) == 1) return {1,delx};
    return {0,1};
}
void init()
{
    int n = 3;
    for(int i=1;i<=3;++i)
    {
        for(int j=1;j<=3;++j) {
            pos[3*(i-1) + j].first = i;
            pos[i + 3*(j-1)].second = i;
        }
    }
    do {
        bool ok = true;
        ok &= check(1,3,2);ok &= check(1,7,4);
        ok &= check(3,9,6);ok &= check(7,9,8);
        ok &= check(3,7,5);ok &= check(1,9,5);
        ok &= check(2,8,5);ok &= check(4,6,5);
        if(ok == false) continue;
        node tmp;
		for(int i=0;i<3;++i) tmp.dist[i] = 0;
        for(int i=1;i<=9;++i) {
            tmp.id[i] = a[i];
            if(i!=1) {
                PII res = cal(tmp.id[i],tmp.id[i-1]);
                tmp.dist[res.first] += res.second;
            }
        }
        v.push_back(tmp);
    }while(next_permutation(a+1,a+1+9));
    sort(v.begin(),v.end(),cmp);
}
signed main() {
    init();
    int T;cin >> T;
    while(T--) {
        int k;cin >> k;
        for(int i=1;i<=9;++i) cout << v[k-1].id[i] << " ";cout << endl;
    }
    return 0;
}

0 comments

No comments so far...