CCSU training contest（1）

$link$

B LaTeX Expert

思维不难，就是读入有点恶心，用$gets$读一行，然后用$strcmp$判断是否为空行

#include <bits/stdc++.h> #define ll long long #define pi pair<int,int> #define mk make_pair #define pb push_back using namespace std; const int maxn = 1e5+100; char a[maxn],A[maxn]; struct node{ string s; int id; }t[maxn]; struct node1{ char s[maxn]; int id; bool operator < (const node1 & t)const { return id < t.id; } }tmp[105]; map<string,int>mp; int main() { int cnt = 0,flag = 0; while(gets(a)){ if(strcmp("\\begin{thebibliography}{99}", a) == 0) { break; } // printf("*%s*",a); for(int i=0;i<strlen(a);i++) { if(a[i] == '{') { if(flag == 0)flag = 1; } else if(a[i] == '}')flag = 0,++cnt; else if(flag == 1) { t[cnt].s += a[i]; } } } for(int i=0;i<cnt;i++) { mp[t[i].s] = i; } int tot = 0; flag = 0; string ttt=""; // puts("DDD!!!!!!!!!!!!!!!!!!!!!"); while(gets(a)) { if(strcmp("\\end{thebibliography}", a) == 0) { break; } if(strcmp(a , "")==0)continue; strcpy(tmp[++tot].s,a); // printf("*"); // puts(tmp[tot].s); for(int i=0;i<strlen(tmp[tot].s);i++) { if(tmp[tot].s[i] == '{') { ttt = ""; if(flag == 0)flag = 1; } else if(tmp[tot].s[i] == '}') { flag = 0; tmp[tot].id = mp[ttt]; } else if(flag == 1) { ttt += tmp[tot].s[i]; } } } // for(int i=1;i<=tot;i++)cout<<tmp[i].s<<' '<<tmp[i].id<<'\n'; cnt = 0; flag = 1; for(int i=1;i<=tot;i++) { if(tmp[i].id != cnt++) { flag = 0; break; } } if(flag == 0) { puts("Incorrect"); sort(tmp+1,tmp+tot+1); puts("\\begin{thebibliography}{99}"); for(int i=1;i<=tot;i++)printf("%s\n",tmp[i].s); puts("\\end{thebibliography}"); } else puts("Correct"); return 0; }

I Minimal Product

题意：先通过题目给的添加求出$A$数组，然后求满足$i<j$ && $a[i]<a[j]$ && $a[i]\ast a[j]$的最小值。 题解：求$A$数组的时候，有个地方要对2的32次方取模，我们可以利用$unsigned-int$自动取模，因为它的范围是0-2^32 - 1,算的时候自动溢出就相当于取模了。那个条件，对于正数来说维护前缀最小值。对于负数来说，维护比他小的前缀最大值，就是倒着维护后缀最大值。

#include <bits/stdc++.h> #define ll long long #define pi pair<int,int> #define mk make_pair #define pb push_back using namespace std; const int maxn = 1e7+10; unsigned int b[maxn]; ll a[maxn]; ll ans[maxn]; int main() { int T; cin >> T; while(T--) { ll n,l,r; unsigned int x,y,z; cin >> n >> l >> r >> x >> y >> z >> b[1] >> b[2]; for(int i=3;i<=n;i++) { b[i] = (x*b[i-2] + b[i-1]*y + z); } for(int i=1;i<=n;i++) { a[i] = b[i]%(r-l+1)+l; // printf("%d ",a[i]); } ll mi = 1e18,ma = -1e18; ll ans = 4e18; for(int i=1;i<=n;i++) { if(a[i] >= 0 && a[i] > mi)ans = min(ans , a[i]*mi); mi = min(a[i],mi); } for(int i = n;i >=1;i--) { if(a[i] <= 0) { if(a[i] < ma)ans = min(ans,a[i]*ma); ma = max(ma , a[i]); } } if(ans == 4e18)puts("IMPOSSIBLE"); else printf("%lld\n",ans); } return 0; }

k Right Expansion Of The Mind

题意：一个字符串由$s$串和$t$串，t串无限循环接在s串后面，如果A字符串是B字符串的子串且B字符串也是A字符串的子串，那么就可以分为一组。输出可以分成多少组，并且输出分组方案。

思路：如果t串的字母字母种类不一样，那么他们一定不能分成一组。s串倒着往前遍历，找到第一个位置，这个位置的字母在s串中没有，把他切割开，如果切割开前面的部分一模一样，那么就可以分为一组。

#include <bits/stdc++.h> #define ll long long #define pi pair<int,int> #define mk make_pair #define pb push_back using namespace std; const int maxn = 1e5+10; const int mod = 1e9+7,mod1 = 998244353; const int base = 73,base1 = 47; struct node { int sta,val,val1,id; bool operator < (const node & t)const { if(val == t.val){ if(val1 == t.val1)return sta < t.sta; else return val1 < t.val1; } return val < t.val; } }a[maxn]; vector<int>G[maxn]; int main() { int n; cin >> n; for(int i=1;i<=n;i++) { string s,s1; cin >> s >> s1; int stas = 0; for(int j=0;j<s1.size();j++) { int p = s1[j] - 'a'; stas |= (1<<p); } a[i].sta = stas; a[i].id = i; int flag = -1; for(int j=s.size()-1;j>=0;j--) { int p = s[j] - 'a'; if((stas&(1<<p)) == 0) { flag = j; break; } } int v = 0,v1 = 0; for(int j=0;j<=flag;j++) { int p = s[j]-'a'+1; v = 1ll*base*v%mod + p; v%=mod; v1 = 1ll*base1*v1%mod1 + p; v1%=mod1; } a[i].val = v; a[i].val1 = v1; } sort(a+1,a+1+n); int l = 1,r = 1,cnt = 1; while(r <= n) { if(a[l].val == a[r].val && a[l].val1 == a[r].val1 && a[l].sta == a[r].sta) { G[cnt].pb(a[r].id); r++; } else l = r,cnt++; } cout<<cnt<<'\n'; for(int i=1;i<=cnt;i++) { cout<<G[i].size()<<' '; for(int j=0;j<G[i].size();j++)printf("%d%c",G[i][j],j==G[i].size()-1?'\n':' '); } return 0; }