2020-9-25 大二2020下训练二

没看见多组数据，wa了几发。
这个题是优先队列+贪心

• 先把数组按照$t$从小到大排列好(这里没有用$cmp$,直接在结构体里定义了，比较方便)
• 然后开始遍历。
  • 如果这个结构体的$a[i].t>q.size()$，说明能进优先队列，这里$q.size()$差不多代表目前时间。
  • 反之，按理说应该是进不去优先队列的，但是，我们这里优先队列是按照$v$从小到大排的，先把这个$a[i].v$放进去，队首肯定是$v$最小的，把它弹出来，减掉就可以了（有时候自己减自己）。

#include using namespace std;
const int N=1e6+10;
struct sa{int t;int v;bool operator <(const sa &a) const {return a.t > t;//和实际相反}
}a[N];
int num;priority_queue< int,vector<int>,greater<int>>q;int n;
int main()
{while(cin>>n){for(int i=1;i<=n;i++){cin>>a[i].t>>a[i].v;}sort(a+1,a+1+n);long long sum=0;for(int i=1;i<=n;i++){if(a[i].t>q.size()){sum+=a[i].v;q.push( a[i].v );}else{sum+=a[i].v;q.push( a[i].v );sum-=q.top();q.pop();}}cout<<sum<<endl;while(!q.empty()) q.pop();}return 0;
}

正解是$KMP$.
这里是偷鸡做法。
既然总串是有一个子串多次重复加在一起的，那我们不妨从枚举前缀子串。

• 前缀子串的长度一定是总串长度的因子。
• 枚举到总串的一半长度即可，因为最小为$1$。
• 最后看构造出的字符串是否和原串相等即可。

#include 
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
string s,ss,ans;
int main()
{IOS;while(cin>>s){int maxn=1;ss="";int s_z=s.size();for(int i=0;i<s_z/2;i++){ans="";ss+=s[i];int ss_z=ss.size();int x=s_z/ss_z;if(s_z%ss_z!=0) continue;for(int j=1;j<=x;j++) ans+=ss;if(ans==s) maxn=max(maxn,x);}cout<<maxn<<endl;}return 0;
}

不存在和局的情况，因为奇偶对立。
一路模拟下去即可，在循环里判断$sum$是不是奇数。
什么意思呢？
比如五张牌，$A3366$
$1+3+3=7$是奇数，（往后加的话就没有奇数了）那她就可以取$1+3$，题目说要按顺序取，Song无论怎么取，也取不到偶数。

感觉这题难在处理输入上。。。是我太菜了

#include using namespace std;
int check(string x){if(x=="10") return 10;if(x[0]>='2' && x[0]<='9') return x[0]-'0';if(x[0]=='A') return 1;if(x[0]=='J') return 11;if(x[0]=='Q') return 12;if(x[0]=='K') return 13;
}
int t,n;
string x;
int main()
{cin>>t;for(int j=1;j<=t;j++){int f=0;cin>>n;int sum=0;for(int i=1;i<=n;i++){cin>>x;sum+=check(x);if(sum&1) f=1;}if(f) printf("Case #%d: Girl\n",j);else printf("Case #%d: Song\n",j);}return 0;
}
/*
2
5
J Q K 10 4
5
2 5 6 8 K
*/

最短路+反向建边
和洛谷的 P1629 邮递员送信很像，题解在这，这里就不写了。

#include
using namespace std;const int maxn=1e6+10;
const int inf=0x3f3f3f3f;
struct sa{int dis;int pos;
};
bool operator <(const sa &a,const sa &b) { return a.dis>b.dis; }priority_queue<sa>q;struct Edge
{int to, w, next;
}edge[maxn];
int head[maxn];
int cnt;
void add_edge(int u, int v, int w)
{edge[cnt].to = v;edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt++;
}int dis[maxn];
bool vis[maxn];
int n,m,s,u,v,w;void dijkstra(int s){memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis));dis[s]=0;q.push( (sa) {0,s});while(!q.empty()){sa ns=q.top();q.pop();int x=ns.pos;if(vis[x]) continue;vis[x]=1;for(int i=head[x]; i!=-1 ; i=edge[i].next){if(dis[edge[i].to]>dis[x]+edge[i].w){dis[edge[i].to]=dis[x]+edge[i].w;q.push( (sa) {dis[edge[i].to],edge[i].to});}}}
}
vector<int> vv;
int t,k,x;
int main()
{cin>>t;for(int j=1;j<=t;j++){int f=0;memset(head,-1,sizeof(head));memset(vis, 0, sizeof(vis));memset(dis, 0, sizeof(vis));vv.clear();cin>>n>>m>>k;//n=read();m=read();s=read();for(int i=1; i<=m; i++){cin>>u>>v>>w;//u=read();v=read();w=read();add_edge(u,v,w);add_edge(v+n,u+n,w);}long long ans=0;for(int i=1;i<=k;i++){cin>>x;if(x!=1)vv.push_back(x);}dijkstra(1);for(auto i:vv){if(dis[i]==inf){printf("Case #%d: QAQ\n",j);f=1;break;}ans+=dis[i];}if(f) continue;dijkstra(1+n);for(auto i:vv){if(dis[i+n]==inf){printf("Case #%d: QAQ\n",j);f=1;break;}ans+=dis[i+n];}if(!f) printf("Case #%d: %lld\n",j,ans);}return 0;
}