A. Working Week
直接输出 即可。
Code
using namespace std; //========================================== typedef long long ll; signed main(signed argc, char const *argv[]) { freopen("in.in", "r", stdin); freopen("out.out", "w", stdout); auto c1 = chrono::high_resolution_clock::now(); ios::sync_with_stdio(false); cin.tie(nullptr); //====================================== int t; cin>>t; while(t--) { int n; cin>>n; cout<<n/3-2<<endl; } //====================================== auto c2 = chrono::high_resolution_clock::now(); cerr<<"Time Used:"<<chrono::duration_cast<chrono::milliseconds>(c2-c1).count()<<"ms"<<endl; return 0; }
B. Tea with Tangerines
找到最小一片橘子皮，设其大小为 ，则其他橘子皮（设大小为 ）对答案的贡献为 。
Code
using namespace std; //========================================== signed main(signed argc, char const *argv[]) { freopen("in.in", "r", stdin); freopen("out.out", "w", stdout); auto c1 = chrono::high_resolution_clock::now(); ios::sync_with_stdio(false); cin.tie(nullptr); //====================================== int t; cin>>t; while(t--) { int n; cin>>n; vector<int> v(n); for(int i=0;i<n;i++) cin>>v[i]; int cnt = 0; for(size_t i=1;i<v.size();i++) cnt += (v[i]-1)/(v.front()*2-1); cout<<cnt<<endl; } //====================================== auto c2 = chrono::high_resolution_clock::now(); cerr<<"Time Used:"<<chrono::duration_cast<chrono::milliseconds>(c2-c1).count()<<"ms"<<endl; return 0; }
C. Phase Shift
遍历字符串中的每个字母 ，若已知其前方字母则直接输出，否则贪心地选择尽量小、没有后项、且与 连接后不会成一个大小小于 的环的字母作为其前方字母。使用两个哈希表维护一个字母的前后项，判环可以使用并查集维护。
Code
using namespace std; //========================================== signed main(signed argc, char const *argv[]) { freopen("in.in", "r", stdin); freopen("out.out", "w", stdout); auto c1 = chrono::high_resolution_clock::now(); ios::sync_with_stdio(false); cin.tie(nullptr); //====================================== int t; cin>>t; while(t--) { int n; cin>>n; string s; cin>>s; unordered_map<char,char> frt, nxt; vector<int> fa(150); iota(fa.begin(), fa.end(), 0); function<int(int)> find = [&](int x) { return fa[x]==x?x:fa[x]=find(fa[x]); }; int cnt = 26; for(auto c : s) { if(frt[c]) cout<<frt[c]; else { for(char p='a';p<='z';p++) { if(nxt[p]) continue; if(cnt>1&&find(p)==find(c)) continue; fa[find(p)] = find(c); nxt[p] = c; frt[c] = p; cout<<p; cnt--; break; } } } cout<<endl; } //====================================== auto c2 = chrono::high_resolution_clock::now(); cerr<<"Time Used:"<<chrono::duration_cast<chrono::milliseconds>(c2-c1).count()<<"ms"<<endl; return 0; }
D. Meta-set
一个 Meta-set 中必定包括两个好牌组，且两个好牌组只能有一张重复的牌，我们称这张重复的牌为“中心牌”，则若某张牌出现在了 个好牌组中，以其为中心牌的 Meta-set 即有 个。
考虑如何获取 值，我们只需要遍历每个牌对，并求出这两张牌的补集，并将补集的 值加一即可。这个过程可以使用哈希表来维护。
Code
using namespace std; //========================================== typedef long long ll; ll hs(const vector<int>& v) { ll sum=0, mul=1; for(int i=v.size()-1;i>=0;i--,mul*=3) sum += v[i]*mul; return sum; } unordered_map<ll,ll> mp; signed main(signed argc, char const *argv[]) { freopen("in.in", "r", stdin); freopen("out.out", "w", stdout); auto c1 = chrono::high_resolution_clock::now(); ios::sync_with_stdio(false); cin.tie(nullptr); //====================================== int n,k; cin>>n>>k; vector<vector<int>> cards(n, vector<int>(k)); for(int i=0;i<n;i++) for(int j=0;j<k;j++) cin>>cards[i][j]; for(int i=1;i<n;i++) { for(int j=0;j<i;j++) { vector<int> v(k); for(int l=0;l<k;l++) { if(cards[i][l]==cards[j][l]) v[l] = cards[i][l]; else v[l] = 3-cards[i][l]-cards[j][l]; } mp[hs(v)]++; } } ll sum = 0; for(auto& v : cards) { auto it = mp.find(hs(v)); if(it==mp.end()) continue; sum += it->second*(it->second-1)/2; } cout<<sum<<endl; //====================================== auto c2 = chrono::high_resolution_clock::now(); cerr<<"Time Used:"<<chrono::duration_cast<chrono::milliseconds>(c2-c1).count()<<"ms"<<endl; return 0; }